Recursion tree method examples ppt

recursion in c programming ppt and ppt recursion in data structure
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures The mechanics of Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering recursion University of Waterloo Waterloo, Ontario, Canada Part 1 ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.The mechanics of recursion, part 1 2 Outline This topic will step through a recursive function call of the Simple_tree class – We will recursively calculate size() on a tree – We will be looking at the memory stack to see how local variables are saved – In the end, the recursion will give us the number of nodes in the treeThe mechanics of recursion, part 1 19.1 3 Recursion We will use the following Simple_tree implementation to demonstrate how recursive functions workThe mechanics of recursion, part 1 19.1 4 Recursion We will use the following Simple_tree implementation to demonstrate how recursive functions work template typename Type class Simple_tree private: Type element; Simple_tree parent; Single_listSimple_tree children; ;The mechanics of recursion, part 1 19.1 5 Recursion Because children is declared as an explicit member variable, all the memory can be allocated together with element template typename Type class Simple_tree private: Type element; Simple_tree parent; Single_listSimple_tree children; ;The mechanics of recursion, part 1 19.1 6 Recursion The tree containing fourteen nodes is represented by a reasonably complex object—assume the root node is stored in a pointer Simple_tree root;The mechanics of recursion, part 1 19.1 7 These diagrams do not include parentThe mechanics of recursion, part 1 19.1 8 Recursion The memory required for such a structure is: 14sizeof(Type) + 14sizeof(int) + 69sizeof(void ); In general, a tree of n nodes would have the memory requirements nsizeof(Type) + nsizeof(int) + (5n - 1)sizeof(void );The mechanics of recursion, part 1 19.1 9 Recursion We will go through, step-by-step, what happens in memory when a recursive call to int size() is made: template typename Type int Simple_treeType::size() const int s = 1; for ( Single_nodeSimple_tree ptr = children.head(); ptr = 0; ptr = ptr-next() ) s += ptr-retrieve()-size(); return s; The mechanics of recursion, part 1 19.1 10 Recursion This function has – two explicit local variables, and – one implied local variable These are int s; Single_nodeSimple_tree ptr Simple_tree const this Recall that every time a member function of Simple_tree is called, the local variable this is assigned the address of the object on which the call is madeThe mechanics of recursion, part 1 19.1 11 Recursion M.C. Hammer was right: you can’t touch this—it’s declared constant – The type depends on what a member function is called on... – Clearly Stanley Burrell was an early adopter of C++ Simple_tree const this M.C. Hammer/EMI http://www.youtube.com/watch?v=otCpCn0l4WoThe mechanics of recursion, part 1 19.1 12 Recursion From ECE 222, you know that memory for local variables is assigned on a stack – Each time a function is called, memory for that function is pushed on top of the stack In ECE 222, you will see many other items that are placed onto the stack – For example, the memory location of where to jump to when the function returns We will focus on simply the abstract memory locationsThe mechanics of recursion, part 1 19.1 13 Example Suppose the local variable root is assigned the address of the root of our tree: 00015b10 The first thing to occur is that some function must call int h = root-size(); root-size(); The mechanics of recursion, part 1 19.1 14 Example Suppose the local variable root is assigned the address of the root of our tree: 00015b10 The first thing to occur is that some function must call int h = root-size(); root-size(); The mechanics of recursion, part 1 19.1 15 Example Memory is allocated on the stack for the call to size call with memory for this, s, and ptr The implicit local variable this is assigned the address of the node Simple_tree const this int Simple_tree::size() const int s = 1; for ( Single_nodeSimple_tree ptr = children.head(); A.size() ptr = 0; ptr = ptr-next() ) s += ptr-retrieve()-size(); return s; root-size(); The mechanics of recursion, part 1 19.1 16 Example First, the local variable s is set to 1 – This sets the corresponding location on the stack int Simple_tree::size() const int s = 1; for ( Single_nodeSimple_tree ptr = children.head(); A.size() ptr = 0; ptr = ptr-next() ) s += ptr-retrieve()-size(); return s; root-size(); The mechanics of recursion, part 1 19.1 17 Example First, the local variable s is set to 1 – This sets the corresponding location on the stack The initialization of the for loop calls children.head() – The variable this tells us where to find this linked list int Simple_tree::size() const int s = 1; for ( Single_nodeSimple_tree ptr = children.head(); A.size() ptr = 0; ptr = ptr-next() ) s += ptr-retrieve()-size(); return s; root-size(); The mechanics of recursion, part 1 19.1 18 Example For the call to children.head(), we must allocate new memory on the stack—in this case, it only stores the implicit local variable this – Note that the address is &A + 4 Simple_node Single_list::head() const return list_head; A.size() root-size(); The mechanics of recursion, part 1 19.1 19 Example For the call to children.head(), we must allocate new memory on the stack—in this case, it only stores the implicit local variable this A.size() root-size(); The mechanics of recursion, part 1 19.1 20 Example All this member function does is returns the member variable list_head – This is copied immediately on top of the memory allocated for the calling function Simple_node Single_list::head() const return list_head; A.size() root-size();