# The call stack or what is difficult about recursion

([home](https://github.com/alexhkurz/introduction-to-programming/blob/master/README.md) ... [previous](https://hackmd.io/@alexhkurz/HJHS4NUAI) ... [next](https://hackmd.io/@alexhkurz/ry2Ax1FC8))

In this session we want to understand better how recursion works.

## Introduction

The message of the [session on recursion](https://hackmd.io/@alexhkurz/Hy48XsvpI) was that recursion is easy. In particular, we saw that the mathematical definition

\begin{align}
fib(0) & = 0\\
fib(1) & = 1\\
fib(n+2) & = fib(n) + fib(n+1)
\end{align}

and the recursive program (in Haskell)

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

are almost identical. And in Python it is only slightly less convenient (because Python does not offer pattern matching).

But there is a sense in which recursive programs are difficult to understand. The reason is that the order in which the operations are executed (the so-called control flow) is not easily visible from the code.

To get started recall the tree

fib(6)
|
+
/ \
fib(4) fib(5)
| |
+ +
/ \ / \
... ...

Before you start the next activity, complete the tree above using pen and paper.

In fact, for what we want to do in this session, we can shorten the tree to in the following way:

fib(6)
/ \
fib(4) fib(5)
/ \ / \
... ...

We may call the tree above the **call tree**, since it shows all the recursive calls to the function `fib`

**Remark:** At no point during the execution of the program the full tree above will be built. The tree is rather a mathematical model that allows us to understand better how the recursion works. In fact, at each point of time, only one of the branches is actually represented (on what is known as the so-called **call stack**).

Before starting on the next activity, it is worth going again through the [computation of $fib(6)$](https://hackmd.io/@alexhkurz/HJiulVg0U) via rewriting and the call stack.

## Tracing the Execution through the Call Tree

Roughly speaking, the program will traverse (=go through) the tree by recursively repeating the pattern **(go left-down, go right-down, return to the middle)**. What counts as left and what count as right here is determined by the line (using Haskell syntax)

fib n = fib (n-2) + fib (n-1)

Here, `fib (n-2)` is called before `fib (n-1)`, so we write `fib (n-2)` on the left and `fib (n-1)` on the right.

**Activity:** The purpose of the next activity is to let the program print out how it traverses (= goes through) the tree.
- Can you add `print` statements to the program [recursive_fib.py](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/recursive_fib.py) so that it outputs

fib 6
fib 4
fib 2
fib 0
fib 1
fib 3
fib 1
fib 2
fib 0
fib 1
fib 5
fib 3
fib 1
fib 2
fib 0
fib 1
fib 4
fib 2
fib 0
fib 1
fib 3
fib 1
fib 2
fib 0
fib 1

when you call $fib(6)$? (To print the string `fib` as well as the number, use `print('fib',n)`.)

- Does your program print `8` at the end? If yes, how do you have to change the program, so that it doesn't?

- Put your finger on the root `fib(6)` of the tree and trace the output of the program through the tree. Describe in your own words the "strategy" that the program uses to traverse the tree.

- How do you have to change your program so that it prints

fib 6
fib 5
fib 4
fib 3
fib 2
fib 1
fib 0
fib 1
fib 2
fib 1
fib 0
fib 3
fib 2
fib 1
fib 0
fib 1
fib 4
fib 3
fib 2
fib 1
fib 0
fib 1
fib 2
fib 1
fib 0

Again trace this output through the tree with your finger.

**Optional Exercise:** How would you describe the following traversal of the tree in your own words?

fib 4 fib 5
fib 2 fib 3
fib 0 fib 1
fib 1 fib 2
fib 0 fib 1
fib 3 fib 4
fib 1 fib 2
fib 0 fib 1
fib 2 fib 3
fib 0 fib 1
fib 1 fib 2
fib 0 fib 1

Can you modify your program so that it produces this output?

## Further reading

Go again through the [commputation of $fib(6)$](https://hackmd.io/@alexhkurz/HJiulVg0U).

## References for the record

[The call graph](https://en.wikipedia.org/wiki/Call_graph)

[The call stack](https://en.wikipedia.org/wiki/Call_stack)