Recursion

is the most powerful and fundamental construction for programming computers. You can write any program with just recursion and branching (if statement). We cannot say the same about loops like a for loop (next chapter).

Let’s write a procedure that returns the $n^{th}$ fibonacci number.

fibonacci_recursive :: proc(n: int) -> int {
	if n == 0 || n == 1 {
		return n
	}
	return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
}

If statement

We can conditionally execute code with if.

// cond is of type boolean (either true or false)
if cond {
	// this block of code gets executed when cond is true	
}

== checks for equality. n == 0 is true when n is 0. || is the or operator. n == 0 || n == 1 is true when at least one of the conditions is met i.e. when n is either 0 or 1.

Tracing our code

Recursion might seem strange at first like a snake eating its own tail. How can a procedure call itself?

Let’s trace what happens when you run fibonacci_recursive(3). Let’s call fibonacci_recursive F for short.

• Computing F(3)

  • The procedure first checks if n is less than or equal to 1. Nope.
  • It reaches the line F(3-1) + F(3-2).
  • Computing F(3-1) = F(2)
    • Now we call F(2). 2 is not 0 or 1. So now we reach the line F(2-1) + F(2-2).
    • Computing F(2-1) = F(1)
      • return 1
    • Computing F(2-2) = F(0)
      • return 0
    • return 1 + 0
  • Computing F(3-2) = F(1)
    • return 1
  • return 1 + 1

  So in the end we get F(3) = 2. In this way, the computer can calculate larger fibonacci numbers like F(10).

The execution flow resembles a tree. I put numbers to indicate the sequence of procedure calls.

flowchart TD;
a["F(3)"] -.1.-> b["F(2)"];
b -.2.-> d["F(1)"];
d -.3.-> b;
b -.4.-> e["F(0)"];
e -.5.-> b;
b -.6.-> a;
a -.7.-> c["F(1)"];
c -.8.-> a;
a -.9.-> out([Output = 2]);

style out stroke-width:0;

Stack overflow

When we call a proc, the computer allocates a constant chunk of memory to this procedure. It’s called a stack frame. The stack frame contains the state of the proc - all its data and state of execution. Once the proc returns, the stack frame is destroyed.

When F(10) recursively calls F(9) and F(8). The stack frames for F(9) and F(9) will be inside the stack frame for F(10). Since the outer stack frame has constant memory, as we keep going deeper, we may run out of memory. This is called a stack overflow.

We can cause a stack overflow by calling F(1000). Avoid recursion as much as possible to prevent this error. We will see a better approach to compute the fibonacci sequence in the next chapters.

Asymptotic Analysis

The procedure fibonacci_recursive compares n with 0 and 1. Then it calls itself recursively with n-1 and n-2 as inputs. Let’s say the comparisons take C time. The procedure takes T(n) time. We get:

$$T(n)=C+T(n-1)+T(n-2)$$

To find the exact value of T, we need a more elaborate analysis. Since $$T(n-1)>T(n-2)$$, We can say that T is at least as large as this other function.

$$\begin{array}{rl}T(n)& =C+T(n-1)+T(n-2)\\ & \ge C+2T(n-2)\end{array}$$

Let’s substitute the value of T(n-1) recursively in this equation.

$$\begin{array}{rl}T(n)& \ge C+2T(n-2)\\ & \ge C+2C+4T(n-4)\\ & \ge 3C+4T(n-4)\\ & \ge 2^{k-1}C+2^{k}T(n-2k)\end{array}$$

When n is even and $2k=n$ we get,

$$\begin{array}{rl}T& \ge 2^{\frac{n}{2}-1}C+2^{\frac{n}{2}}T(0)\\ & \ge 2^{\frac{n}{2}}{C}_1\end{array}$$

Since $T(0)$ is a constant. If n is odd, we will be left with T(1) but the asymptotic bound will remain the same. (Try it out!)

Conclusion: This algorithm takes exponential time and is extremely slow for large inputs. We get the same equation for memory usage because of recursive stack frames.

Exercise

Call this proc in main and experiment. Pass various values of n to fibonacci_recursive. You can measure execution time by running:

$ time odin run .

Do you think the time is increasing exponentially? What is the 40th fibonacci number and how long did your computer take to calculate it?