Recursion

  call factorial(4), depth 1
    call factorial(3), depth 2
      call factorial(2), depth 3
        call factorial(1), depth 4
        base case, returning 1
      factorial(2) returns 2
    factorial(3) returns 6
  factorial(4) returns 24
factorial(4) is 24

Five calls are alive at the deepest point, each with its own n. That is the answer to "how does recursion work": the same code, several sets of variables, one per call.

%*s prints an empty string padded to a width given as an argument, which is a tidy way to indent by depth. It is not part of the lesson; it is how the trace was produced.

Recursion against iteration

#include <stdio.h>

unsigned long long fact_loop(int n)
{
    unsigned long long f = 1;
    for (int i = 2; i <= n; i++) {
        f = f * (unsigned long long) i;
    }
    return f;
}

unsigned long long fact_rec(int n)
{
    return n <= 1 ? 1 : (unsigned long long) n * fact_rec(n - 1);
}

int main(void)
{
    for (int n = 5; n <= 20; n += 5) {
        printf("%2d! loop %20llu   recursive %20llu   same? %s\n",
               n, fact_loop(n), fact_rec(n),
               fact_loop(n) == fact_rec(n) ? "yes" : "no");
    }
    return 0;
}

 5! loop                  120   recursive                  120   same? yes
10! loop              3628800   recursive              3628800   same? yes
15! loop        1307674368000   recursive        1307674368000   same? yes
20! loop  2432902008176640000   recursive  2432902008176640000   same? yes

Anything recursive can be written iteratively and anything iterative can be written recursively. The choice is about which one says what the problem is. Factorial is genuinely recursive in its definition and is still better written as a loop, because a loop expresses "multiply these numbers together" and costs nothing.

The one where recursion is a disaster: Fibonacci

MU sets Fibonacci as Practical 3(c), and chapter 28 wrote it as a loop. The recursive version is the standard example of recursion done badly, and the cost is worth measuring rather than being told.

#include <stdio.h>

long long calls = 0;

long long fib_rec(int n)
{
    calls++;
    if (n < 2) {
        return n;
    }
    return fib_rec(n - 1) + fib_rec(n - 2);
}

long long fib_loop(int n)
{
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main(void)
{
    printf("%4s %12s %14s %12s\n", "n", "fib", "calls made", "loop passes");
    for (int n = 5; n <= 35; n += 5) {
        calls = 0;
        long long r = fib_rec(n);
        printf("%4d %12lld %14lld %12d\n", n, r, calls, n);
    }
    printf("\nthe loop gives the same answers:\n");
    for (int n = 5; n <= 35; n += 5) {
        printf("fib(%d) = %lld\n", n, fib_loop(n));
    }
    return 0;
}

   n          fib     calls made  loop passes
   5            5             15            5
  10           55            177           10
  15          610           1973           15
  20         6765          21891           20
  25        75025         242785           25
  30       832040        2692537           30
  35      9227465       29860703           35

the loop gives the same answers:
fib(5) = 5
fib(10) = 55
fib(15) = 610
fib(20) = 6765
fib(25) = 75025
fib(30) = 832040
fib(35) = 9227465

Look at the third column. fib_rec(35) made nearly thirty million calls to compute a number the loop reaches in thirty-five additions. The reason is visible in the tree: fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again. The same sub-problems are recomputed over and over, and the table shows the cost exactly: the call count is multiplied by about eleven for every five added to n, a factor of roughly 1.6 per step. The loop's cost goes up by one.

This is the honest answer to "is recursion good". Recursion is a tool for problems whose sub-problems do not overlap. Where they do overlap, either use a loop or remember the answers, and remembering them is a later semester's topic.

Where recursion is the right answer

Two examples worth having, both short.

#include <stdio.h>
#include <string.h>

/* Reverse a string in place, one pair of characters per call. */
void reverse(char *s, int left, int right)
{
    if (left >= right) {
        return;                         /* base case: met in the middle */
    }
    char t = s[left];
    s[left] = s[right];
    s[right] = t;
    reverse(s, left + 1, right - 1);
}

/* The greatest common divisor, which IS defined recursively. */
int gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

/* The sum of the digits of a number. */
int digit_sum(int n)
{
    if (n < 10) {
        return n;
    }
    return n % 10 + digit_sum(n / 10);
}

int main(void)
{
    char word[] = "recursion";
    reverse(word, 0, (int) strlen(word) - 1);
    printf("reversed : %s\n", word);
    printf("gcd(48, 18) = %d\n", gcd(48, 18));
    printf("gcd(270, 192) = %d\n", gcd(270, 192));
    printf("digit_sum(9875) = %d\n", digit_sum(9875));
    return 0;
}

reversed : noisrucer
gcd(48, 18) = 6
gcd(270, 192) = 6
digit_sum(9875) = 29

gcd is the best example in the chapter. Euclid's algorithm is a recursive statement: the gcd of a and b is the gcd of b and a % b, and the gcd of a and 0 is a. The recursive code is the definition, character for character.

What goes wrong

No base case. The calls never stop.

A base case that is never reached. factorial(-1) with a base case of n == 0 recurses towards minus infinity. n <= 1 is the safer test, and checking for a negative argument is better still.

Too deep. Each call uses stack space, and the stack is finite. Recursion depth of a few thousand is usually safe; a few million is not. A loop has no such limit.

Recomputing the same thing, as Fibonacci does.

What this does NOT mean

Recursion is not a loop. It is repeated function calls, each with its own variables.

Recursion is not more powerful than iteration. Each can express what the other can.

Recursion is not slower because of the arithmetic. It is slower because of the calls and, in the Fibonacci case, because of the repeated work.

A recursive function does not need to return a value. reverse above returns nothing.

The base case is not always n == 0. It is whatever value the function can answer without calling itself.

A function calling another function which calls the first is still recursion. That is indirect recursion, and it needs a base case just as much.

Quick revision

• A recursive function calls itself and needs a base case plus progress towards it.
• Each call has its own parameters and locals, held on the call stack.
• Compute nothing on the way down; the answers are built on the way back up.
• factorial(n): base n <= 1 returns 1, else n * factorial(n - 1).
• gcd(a, b): base b == 0 returns a, else gcd(b, a % b).
• Recursion and iteration can each do the other's job; choose the one that states the problem.
• Naive recursive Fibonacci recomputes sub-problems and the call count is multiplied by about 1.6 per step, so by about eleven every five.
• Missing or unreachable base case, or too great a depth, means a stack overflow.
• Recursion suits trees and genuinely recursive definitions; loops suit the rest.

Test yourself

1. What two things must every recursive function have?

A base case that returns without calling itself, and a recursive case whose argument is closer to the base case.

2. Trace factorial(4).

4 factorial(3), which is 4 (3 factorial(2)), which is 4 (3 (2 factorial(1))). factorial(1) is 1, so the value unwinds as 2, then 6, then 24.

3. What happens if the base case is left out?

The function calls itself for ever, the stack runs out of space, and the program is killed. That is a stack overflow.

4. Write gcd recursively.

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

5. Why is recursive Fibonacci a bad idea?

Because fib(n-1) and fib(n-2) both recompute the same smaller values, so the number of calls grows roughly by a factor of 1.6 per step. The loop version does n additions.

6. How many calls to factorial are alive at the deepest point of factorial(5)?

Six: the calls for 5, 4, 3, 2, 1 and the one that hits the base case, depending on how the base is written. With a base case of n <= 1, five calls are made and the fifth returns without calling again.

7. Can a recursive function be void?

Yes. The reverse function in this chapter returns nothing; the base case simply returns.

What can be asked on this, and how to answer it

"What is recursion? Write a program to find the factorial of a number using recursion." Define it, name the base case and the recursive case, give the program, and then give the trace of factorial(4). The trace is what shows you understand it rather than remember it.

"Write a program using a recursive function." Any of the four in this chapter answers it. gcd is the best choice, because you can say in one line that Euclid's algorithm is itself recursive, so the code is the definition.

"Distinguish between recursion and iteration." Recursion repeats by calling itself, needs a base case, and uses stack space proportional to the depth. Iteration repeats with a loop, needs a terminating condition, and uses fixed memory. Either can do the other's job; recursion suits recursive definitions and trees, iteration suits everything else.

"What is a stack overflow? How does it arise in recursion?" The call stack is the memory holding one frame per live call, and it is finite. A recursion with no base case, an unreachable base case, or too great a depth exhausts it and the program is killed.

"Explain how recursion works internally." Each call gets its own frame on the call stack holding its parameters and local variables. Calls on the way down are suspended and waiting; when the base case returns, each waiting call resumes, combines the returned value and returns in turn. Give the indented trace.