Log in / Register
Home arrow Computer Science arrow Data Structures and Algorithms with Python
< Prev   CONTENTS   Next >

3.5 Tracing the Execution of a Recursive Function

Early in this chapter you were given the mandate “Don't think too hard” when writing a recursive function. Understanding exactly how a recursive function works may be a bit difficult when you are first learning about them. It may help to follow the execution of a recursive function in an example. Consider the program in the previous section. Let's assume that the user entered the integer 4 at the keyboard. When this program begins running it will have an activation record on the run-time stack for the module and the main function.

When the program gets to line 10 in the code of Sect. 3.4.2, where the recSumFirstN function is first called, a new activation record will be pushed for the function call, resulting in three activation records on the run-time stack. The Python interpreter then jumps to line 2 with n pointing at the number 4 as shown in the picture of Fig. 3.5. Execution of the function proceeds. The value of n is not zero, so Python executes line 5 where there is another function call to recSumFirstN. This causes the Python interpreter to push another activation record on the run-time stack and the interpreter jumps to line 2 again. This time the value of n is 3. But again, this is not zero, so line 5 is executed and another activation record is pushed with a new value of 2 for n. This repeats two more times for values of 1 and 0 for n.

The important thing to note in this program execution is that there is one copy of the variable n for each recursive function call. An activation record holds the local variables and parameters of all variables that are in the local scope of the function.

Fig. 3.5 The Run-time Stack of a Recursive Function Call

Each time the function is called a new activation record is pushed and a new copy of the local variables is stored within the activation record. The picture in Fig. 3.5 depicts the run-time stack at its deepest point.

When execution of the function gets to the point when n equals 0, the Python interpreter finds that n equals 0 on line 2 of the code. It is at this point that the sumFirstN function returns its first value. It returns 0 to the previous function call where n was 1. The return occurs on line 5 of the code. The activation record for the function call when n was 0 is popped from the run-time stack. This is depicted in Fig. 3.6 by the shading of the activation record in the figure. When the function returns the space for the activation record is reclaimed for use later. The shaded

Fig. 3.6 The First Return from recSumFirstN

object containing 0 on the heap is also reclaimed by the garbage collector because there are no references pointing at it anymore.

After the first return of the RecSumFirstN, the Python interpreter returns to line 5 in the previous function call. But, this statement contains a return statement as well. So, the function returns again. Again, it returns to line 5, but this time with a value of 1. The function returns again, but with a value of 3 this time. Again, since it returned to line 5, the function returns again with a value of 6. Finally, once again the function returns, this time with a value of 10. But this time the recSumFirstN function returns to line 10 of the main function where s is made to point to the value of 10. This is depicted in Fig. 3.7.

Fig. 3.7 The Last Return from recSumFirstN

The program terminates after printing the 10 to the screen and returning from the main function after line 12 and from the module after line 15. The importance of this example is to illustrate that each recursive call to recSumFirstN has its own copy of the variable n because it is local to the scope of the recSumFirstN function. Each time the function is called, the local variables and parameters are copied into the corresponding activation record. When a function call returns, the corresponding activation record is popped off the run-time stack. This is how a recursive function is executed.

Found a mistake? Please highlight the word and press Shift + Enter  
< Prev   CONTENTS   Next >
Business & Finance
Computer Science
Language & Literature
Political science