Recursion, call trees and memoisation

Many DSA algorithms (tree traversal, merge sort, quick sort, depth-first search, backtracking, dynamic programming) are recursive. To analyse them you need one new picture: the call tree.

The cost of recursion = number of calls × work per call

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13…: each is the sum of the two before. The definition turns directly into code:

1long calls = 0;                      // counts every call2 3long Fib(int n)4{5    calls++;6    if (n <= 1) return n;            // base cases: Fib(0) = 0, Fib(1) = 17    return Fib(n - 1) + Fib(n - 2);  // two recursive calls8}9 10Console.WriteLine($"Fib(30) = {Fib(30)}, calls = {calls:N0}");

Fib(30) = 832040, calls = 2,692,537

Short, correct, and terribly slow. Each call does O(1) work, but there are millions of calls. Draw the calls as a tree and the reason is obvious:

Every call splits into two, so the tree roughly doubles in size with each extra n: O(2ⁿ) calls (more precisely about 1.6ⁿ). Most of them are repeats: Fib(2) is calculated again and again.

Memoisation: remember answers you already have

If a recursive method is called with the same argument many times and always returns the same answer, store each answer the first time and look it up after that. This is called memoisation (from “memo”, a note to yourself).

1static long Fib(int n, Dictionary<int, long> memo)2{3    if (n <= 1) return n;4    if (memo.TryGetValue(n, out long known)) return known;   // already solved5 6    long result = Fib(n - 1, memo) + Fib(n - 2, memo);7    memo[n] = result;                                         // remember it8    return result;9}10 11Console.WriteLine(Fib(90, new Dictionary<int, long>()));

2880067194370816120

Now each Fib(k) is calculated once: about 2n calls, O(n) time and O(n) memory for the memo and the stack. Fib(90) is instant, while the plain version would need about 9 billion billion calls.

Or skip recursion: build up from the bottom

Once you see that each value depends only on the two before it, you can compute from the bottom up with a loop and keep just two variables: O(n) time and O(1) space. This bottom-up style is the heart of dynamic programming, which has its own lessons later.

1static long Fib(int n)2{3    long a = 0, b = 1;               // Fib(0), Fib(1)4    for (int i = 0; i < n; i++)5        (a, b) = (b, a + b);         // slide the window forward6    return a;7}8 9Console.WriteLine(Fib(90));

2880067194370816120

Recursion patterns you will meet again

The shape of the call tree tells you the cost. These four shapes cover most algorithms in this course:

Here is a halving recursion. To compute xⁿ, compute x^(n/2) once and square it. Each call halves n, so it needs only about log₂ n calls instead of n multiplications:

1static long Power(long x, int n)2{3    if (n == 0) return 1;4    long half = Power(x, n / 2);     // ONE recursive call on n/25    return n % 2 == 0 ? half * half : half * half * x;6}7 8Console.WriteLine(Power(2, 10));9Console.WriteLine(Power(3, 5));

1024
243

1static long Ways(int n, long[] memo)2{3    if (n <= 1) return 1;4    if (memo[n] != 0) return memo[n];5    return memo[n] = Ways(n - 1, memo) + Ways(n - 2, memo);6}7 8Console.WriteLine(Ways(10, new long[11]));9Console.WriteLine(Ways(50, new long[51]));

89
20365011074