02. Recursion

Solve a Smaller Version of the Same Problem#

Recursion means a function calls itself, directly or through another function. The useful idea is that a solution to a smaller input can become part of the solution to the original input. You need a base case, whose answer is available without another recursive call, and a recursive case that moves towards it.

For a nonnegative integer n, factorial is the product from 1 through n, with 0! = 1. Therefore n! = n × (n-1)! when n > 0.

unsigned long long factorial(unsigned n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

For exact answers in a 64-bit unsigned long long, restrict this example to n <= 20. Unsigned multiplication wraps on overflow, so a larger result would no longer represent the mathematical factorial. The base case handles zero; every remaining call decreases n by one, guaranteeing termination for the stated domain.

Practice. Why would changing the recursive argument to n + 1 break this algorithm? Is having an if (n == 0) enough?

Winding and Unwinding#

Each call has its own execution state, commonly stored in a stack frame: its parameter values, local state and where to resume its caller. A caller pauses while its recursive call runs. It resumes after that call returns.

The boxes show pending work. factorial(4) cannot multiply by the answer to factorial(3) until that answer exists. At the deepest point, calls for 4,3,2,1,0 are simultaneously active. The base call returns 1, starting unwinding.

Notice how the stored factors do not change while lower calls run. There is a separate n for every invocation, not one shared n being repeatedly overwritten.

Work Before and After the Call#

#include <stdio.h>

void show(unsigned n) {
    if (n == 0) return;
    printf("before %u\n", n);
    show(n - 1);
    printf("after %u\n", n);
}

show(3) prints before 3, before 2, before 1, then after 1, after 2, after 3. Code before the recursive call runs on the way down; code after it runs on the way back. A recursive call does not jump permanently to the next invocation: the caller still has work to complete.

Practice. What does show(1) print, and why is there no line for zero?

Recursing Over Linked Lists#

A finite acyclic list is empty or a node followed by a shorter list. If sum(tail) is already correct, the whole sum is the first value plus that tail sum. Use the struct node from C and Linked Lists:

long long listSum(const struct node *head) {
    if (head == NULL) return 0;
    return head->value + listSum(head->next);
}

On the lecture's values 12,5,19,20, the calls descend to the empty suffix. Returns are 0, 20, 39, 44, 56. The sum of the empty list is zero because zero is the identity for addition: adding it changes nothing.

To justify correctness, use induction on list length. For length zero the answer is correct. Assume the function correctly sums any list of length n-1. A list of length n has one first value and a suffix of length n-1; adding that first value to the recursive suffix result sums every node exactly once. Because the suffix length decreases, the calls terminate. Assume the answer fits the return type.

Print Forward or Backward#

void printForward(const struct node *head) {
    if (head == NULL) return;
    printf("%d\n", head->value);
    printForward(head->next);
}

void printReverse(const struct node *head) {
    if (head == NULL) return;
    printReverse(head->next);
    printf("%d\n", head->value);
}

For 4,5,7, forward prints 4,5,7; reverse first reaches the end and then prints 7,5,4. Reverse printing changes the order of output, not any list link. Both visit each node once and use one active call per node at their deepest point.

Practice. Implement “print every second item”, starting with the head. What must you check before stepping two links?

Practice. Retrieve zero-based position i recursively without confusing an absent value with an integer zero.

Helpers Carry the Missing State#

A public function may take a wrapper while recursion needs a node, or it may omit state that the recursive step needs. A helper function supplies those details without changing the public interface.

static struct node *doListAppend(struct node *head, int value) {
    if (head == NULL) return newNode(value);
    head->next = doListAppend(head->next, value);
    return head;
}

void listAppend(struct list *list, int value) {
    list->head = doListAppend(list->head, value);
}

Here the wrapper is deliberately struct list { struct node *head; };, with newNode from the foundations chapter. If your wrapper also caches a tail or size, this excerpt needs the corresponding updates. On 4,5, the empty suffix creates the node 7; the returning call at 5 stores 7 as its next pointer; the returning call at 4 retains 5 as its successor. Returning the updated subtree/list root is a general pattern you will use in tree insertion and deletion.

Numbered printing needs a changing counter. The public function starts it once:

static void doPrintNumbered(const struct node *head, unsigned number) {
    if (head == NULL) return;
    printf("%u. %d\n", number, head->value);
    doPrintNumbered(head->next, number + 1);
}

void printNumberedList(const struct node *head) {
    doPrintNumbered(head, 1);
}

For 34,38,55, output is 1. 34, 2. 38, 3. 55. Restarting the counter inside every call would print 1 every time. Passing it as a parameter makes the relationship explicit: it is the number assigned to this suffix's first node.

Practice. Why must recursive append assign head->next = ... rather than just call the helper and discard its return value?

Time, Stack Space and Iteration#

If each call performs constant local work and makes one call on a list one node shorter, total time satisfies T(n) = T(n-1) + O(1). Expanding gives n constant contributions plus the base case: linear time. The maximum number of simultaneously active calls is n+1, including the null-suffix call, so auxiliary stack space is linear too.

An iterative sum can use one pointer and accumulator, giving the same linear time with constant auxiliary space. Recursion's advantage is a direct expression of recursive structure, especially when a tree splits into multiple subtrees. Its cost includes frames and call overhead. Do not assume a compiler will eliminate recursive stack use. Total number of calls measures time; maximum active depth measures stack space. They need not be the same: a balanced tree traversal makes linear total calls but only logarithmic active depth.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. For a recursive list length function, identify the base case, smaller input and return expression. What happens to stack space on a list of length n?

Question 2. A function prints head->value, recurses on head->next, then prints head->value again. What prints for 1 -> 2 -> 3 and why?

Question 3. Why is return recurse(head->next); not a valid generic fix for processing a cyclic linked list?