Question? Leave a message!




The mechanics of recursion

The mechanics of recursion
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 © 20062013 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 Simpletree 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 Simpletree implementation to demonstrate how recursive functions workThe mechanics of recursion, part 1 19.1 4 Recursion We will use the following Simpletree implementation to demonstrate how recursive functions work template typename Type class Simpletree private: Type element; Simpletree parent; SinglelistSimpletree 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 Simpletree private: Type element; Simpletree parent; SinglelistSimpletree 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 Simpletree 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, stepbystep, what happens in memory when a recursive call to int size() is made: template typename Type int SimpletreeType::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); ptr = 0; ptr = ptrnext() ) s += ptrretrieve()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; SinglenodeSimpletree ptr Simpletree const this Recall that every time a member function of Simpletree 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++ Simpletree const this M.C. Hammer/EMI http://www.youtube.com/watchv=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 = rootsize(); rootsize(); 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 = rootsize(); rootsize(); 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 Simpletree const this int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); 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 Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); 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 Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); 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 Simplenode Singlelist::head() const return listhead; A.size() rootsize(); 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() rootsize(); The mechanics of recursion, part 1 19.1 20 Example All this member function does is returns the member variable listhead – This is copied immediately on top of the memory allocated for the calling function Simplenode Singlelist::head() const return listhead; A.size() rootsize(); The mechanics of recursion, part 1 19.1 21 Example We now return to the calling function – We take the return variable and assign it to ptr int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 22 Example The value stored immediately above the memory allocated for the current function call is copied to the memory allocated for ptr int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 23 Example We evaluate ptr = 0, determine this returns true, and we therefore proceed into the loop int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 24 Example We evaluate ptr = 0, determine this returns true, and we therefore proceed into the loop The first thing we do in the loop is call ptrretrieve() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 25 Example In this call to retrieve(), this is assigned the address of the node in question Simpletree Singlenode::retrieve() const return element; A.size() rootsize(); The mechanics of recursion, part 1 19.1 26 Example In this call to retrieve(), this is assigned the address of the node in question A.size() rootsize(); The mechanics of recursion, part 1 19.1 27 Example The entry under element is copied to the location of the return value Simpletree Singlenode::retrieve() const return element; A.size() rootsize(); The mechanics of recursion, part 1 19.1 28 Example We now return to the calling function – We don’t store this value; instead, we immediately recursively call size() on the node stored at this location int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 29 Example So now we have a second call to size() – We must allocate memory for the three local variables this, s, and ptr and this is assigned the address of the object we are calling size() on—in this case, node B – Note that in this function call, we have no access to any of the local variables of the initiating call to size() on node A B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 30 Example Like before, we step through the function and begin by initializing s B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 31 Example Like before, we step through the function and begin by initializing s Again, we initialize the loop, but to the liked list associated with this node B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 32 Example The call to children.head() will return the listhead of this singly linked list B.size() A.size() rootsize(); The mechanics of recursion, part 1 19.1 33 Example The call to children.head() will return the listhead of this singly linked list The return value is 0004fd48 and this will be placed on top of the stack B.size() Simplenode Singlelist::head() const return listhead; A.size() rootsize(); The mechanics of recursion, part 1 19.1 34 Example The return value is assigned to the ptr associated with this function call B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 35 Example The return value is assigned to the ptr associated with this function call – We check that ptr = 0 and proceed to the body of the loop B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 36 Example The call to retrieve() returns a pointer to the first child of node B – children is a linked list of pointers B.size() Simpletree Singlenode::retrieve() const return element; A.size() rootsize(); The mechanics of recursion, part 1 19.1 37 Example The return value to retrieve() is again, left on top of the stack and we will recursively call size on the node at that address B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 38 Example The first child of node B is node D – As before, we set up three entries on the stack for local variables D.size() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 39 Example Looking at where we are in the tree D.size() B.size() A.size() rootsize(); The mechanics of recursion, part 1 19.1 40 Example We initialize the local variable s for this function call D.size() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 41 Example We initialize the local variable s for this function call Again, we must also access the head of this linked list D.size() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 42 Example With this call, we now return 00000000 D.size() B.size() Simplenode Singlelist::head() const return listhead; A.size() rootsize(); The mechanics of recursion, part 1 19.1 43 Example The return value is copied to the top of the stack and we return to size() called on node D – The return value is copied to the location for ptr D.size() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 44 Example The return value is copied to the top of the stack and we return to size() called on node D – The return value is copied to the location for ptr In this case, ptr = 0 returns false D.size() – We jump to the return statement B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 45 Example Because we are returning, we must copy the return value to the location immediately above the memory allocated for calling function D.size() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 46 Example We are just finished the call to – ptrretrieve()size() where ptr had the address of node D We must now deal with this return value B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 47 Example In this case, we add it to the local variable s B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 48 Example At this point, we have finished executing the body of this loop—we next proceed to the increment statement : ptr = ptrnext() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 49 Example At this point, we have finished executing the body of this loop—we next proceed to the increment statement : ptr = ptrnext() B.size() A.size() rootsize(); The mechanics of recursion, part 1 19.1 50 Example Again, we start with a function call on the node stored at 0004fd48—this requires information placed onto the stack – The address 0005fa58 is the return value B.size() Simpletree Singlenode::next() const return nextnode; A.size() rootsize(); The mechanics of recursion, part 1 19.1 51 Example The return value is copied to the memory location for ptr B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 52 Example The return value is copied to the memory location for ptr – The test ptr = 0 evaluates to true, so we continue into the body B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 53 Example We call ptrretrieve() on this node in the body of the for loop – This will return the address 00052750 B.size() Simpletree Singlenode::retrieve() const return element; A.size() rootsize(); The mechanics of recursion, part 1 19.1 54 Example We call ptrretrieve() on this node in the body of the for loop – This will return the address 00052750 – We are currently at the second node in the linked list B.size() A.size() rootsize(); The mechanics of recursion, part 1 19.1 55 Example This value is placed on top of the stack – We will proceed to call size() on the tree node at this address B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 56 Example As before, we allocate memory for a call to size() on a tree node – We will repeat the process on tree node E and, in turn, on all its descendants E.size() B.size() A.size() rootsize(); The mechanics of recursion, part 1 19.1 57 Example This is the node we are now recursively calling size() on – Node K has two children, each of which are leaf nodesThe mechanics of recursion, part 1 19.1 58 Example It should be obvious that, at the end, s will be assigned 6 and ptr is assigned 0 – We are at the end of this tree node’s linked list – When ptr = 0 returns false, we end the for loop E.size() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 59 Example In preparation to return, we copy the value of s to the appropriate location E.size() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 60 Example We are now back in tree node B and we add the returned value onto the local variable s for the current function call B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 61 Example We are now back in tree node B and we add the returned value onto the local variable s for the current function call – We are finished executing the body of the loop, so we proceed to ptr = ptrnext() B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 62 Example We call next() on the node at the address ptr – In this case, it is 00000000 B.size() Simpletree Singlenode::next() const return nextnode; A.size() rootsize(); The mechanics of recursion, part 1 19.1 63 Example We call next() on the node at the address ptr – In this case, it is 00000000 – We are at the end of this linked list B.size() A.size() rootsize(); The mechanics of recursion, part 1 19.1 64 Example This value is copied to the memory location of ptr for the function call on tree node B B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 65 Example This value is copied to the memory location of ptr for the function call on tree node B – ptr = 0 evaluates to false, so we end the loop B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 66 Example We prepare to return the value of s by copying its value to the location immediately above the memory for the previous function call B.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 67 Example Now that we’re back in the function call on tree node A, we add the return value onto s: 1 + 8 = 9 int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 68 Example The body of the loop is over; we call next() on the node at the address stored in ptr Simpletree Singlenode::next() const return nextnode; A.size() rootsize(); The mechanics of recursion, part 1 19.1 69 Example The body of the loop is over; we call next() on the node at the address stored in ptr A.size() rootsize(); The mechanics of recursion, part 1 19.1 70 Example The returned value is assigned to ptr int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 71 Example The returned value is assigned to ptr – We note that it is ptr = 0 int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 72 Example The returned value is assigned to ptr – We note that it is ptr = 0 – We call ptrretrieve() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 73 Example This node stores the address of the tree node at 0030230 – This is the value returned Simpletree Singlenode::retrieve() const return element; A.size() rootsize(); The mechanics of recursion, part 1 19.1 74 Example This node stores the address of the tree node at 0030230 – This is the value returned A.size() rootsize(); The mechanics of recursion, part 1 19.1 75 Example We call size() on this tree node int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 76 Example Again, we won’t go through the whole process – After walking through the linked list, we will note that the number of nodes in this tree is 5 C.size() A.size() rootsize(); The mechanics of recursion, part 1 19.1 77 Example By the end, s is assigned 5 and ptr is 00000000 C.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 78 Example The condition ptr = 0 is false, so we prepare to return by copying the value of s into the appropriate location C.size() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 79 Example The calling function adds the return value to so – The new value is 9 + 5 = 14 int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 80 Example The loop is over, so we call ptrnext() int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 81 Example The loop is over, so we call ptrnext() A.size() rootsize(); The mechanics of recursion, part 1 19.1 82 Example The returned value of ptrnext() is copied to the appropriate location for the variable ptr int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 83 Example At this point, ptr = 0 returns false, so we prepare to return by copying the local variable s to the appropriate location int Simpletree::size() const int s = 1; for ( SinglenodeSimpletree ptr = children.head(); A.size() ptr = 0; ptr = ptrnext() ) s += ptrretrieve()size(); return s; rootsize(); The mechanics of recursion, part 1 19.1 84 Example We have returned to whatever function originally called rootsize(); That function can access the value returned by the call, either assigning it, using it as a further function call, or possibly discarding it rootsize(); The mechanics of recursion, part 1 19.1 85 Comments In this example, we have gone stepbystep through these function calls—you may have even noted a few places where optimizations could have occurred – Good compilers will optimize code—you will see more of this in the course ECE 351 CompilersThe mechanics of recursion, part 1 86 Summary In this topic, we have at an indepth study of recursion on a tree – A stepbystep process visiting the various nodes within the tree – The process is very methodological and recursive – If time permits, I will try to prepare slides demonstrating recursion on a binary tree with a more complex functionThe mechanics of recursion, part 1 87 References Wikipedia, http://en.wikipedia.org/wiki/Recursion(computerscience) rd 1 Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3 Ed., Addison Wesley, 1997, §2.2.1, p.238. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017