15.2. Flow of execution of recursive functions

At first glance recursive functions look a little bit strange because it seems that we use something that we have not defined. But remember that the statements in the body of a function are only executed when the function is called. At the definition step, the function is just added in the current namespace. Therefore it will be defined when we call it in the body.

Writing recursive functions is sometimes difficult, because we doubt that we have defined a function executing the specific task, when we call the it . Therefore it is useful to remember this fact during the development of recursive functions.

Stack diagram of recursive functions.  Let's have a deeper look at the flow of execution of recursive functions. Figure 15.1 shows the stack diagram of function calls.

Figure 15.1. Stack diagram of recursive function calls

Figure 15.1 shows that the translate function is called with a cds sequence of decreasing length and the local function namespaces are piled up until the terminal condition is reached.

=> rectranslate("atgattgctggt", code)
===> rectranslate("attgctggt", code)
=====> rectranslate("gctggt", code)
=======> rectranslate("ggt", code)
=========> rectranslate("", code)
=========> return ""
=======> return "G"
=====> return "AG"
===> return "IAG"
=> return "MIAG"
  

Important

Recursive function calls can take a lot of memory space because for each recursive call the local namespace for the given function call has to be stored. It is important to pay attention on this fact because memory space is a limited resource on a computer.

Example 15.1. Factorial

Factorial is a famous example of a recursive definition. In Python, you would define it as:
def fact(n):
    if n == 0 or n == 1:
         return 1
    else:
         return n * fact(n - 1)      
    
Figure 15.2 show the stack of the recursive calls with pending return values (you can fill the missing part of these values from top to bottom to follow the successive computations).

Figure 15.2. Stack diagram of recursive function calls for function fact()

Exercise 15.1. Recursive definition of reverse

Write the recursive definition of the reverse function and draw the stack diagram for the string "atcg".

Solution 15.1