A structured lesson workspace with readable content, hands-on examples, and a clean path to completion.
Single recursion makes one recursive call per invocation. The call depth grows linearly with input size. Multiple recursion makes two or more recursive calls per invocation. The call tree branches, and the total number of calls can grow exponentially. The difference between O(n) and O(2^n) is the difference between a function that handles n=1000 in milliseconds and one that hangs for the heat death of the universe at n=50.
#include <stdio.h>int array_sum(const int *arr, int n) {if (n == 0) {return 0;}return arr[n - 1] + array_sum(arr, n - 1);}int main(void) {int data[] = {1, 2, 3, 4, 5};printf("Sum = %d\n", array_sum(data, 5));return 0;}
Five elements, five recursive calls, five stack frames at maximum depth. Linear. Predictable. Boring in the best way.
#include <stdio.h>#include <time.h>long fib(int n) {if (n <= 1) {return n;}return fib(n - 1) + fib(n - 2);}int main(void) {clock_t start = clock();printf("fib(35) = %ld\n", fib(35));clock_t end = clock();printf("Time: %.3f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);start = clock();printf("fib(40) = %ld\n", fib(40));end = clock();printf("Time: %.3f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);return 0;}
Going from n=35 to n=40 increased the input by 14 percent and the time by roughly 1100 percent. That is exponential growth. fib(40) makes approximately 331 million function calls to compute a single number. fib(50) would take minutes. fib(100) would outlive your hardware. The problem is redundant computation: fib(38) is computed once by fib(40) and again by fib(39), and each of those recomputes fib(37), and so on.
#include <stdio.h>#include <time.h>long fib_iter(int n) {if (n <= 1) return n;long prev = 0, curr = 1;for (int i = 2; i <= n; i++) {long next = prev + curr;prev = curr;curr = next;}return curr;}int main(void) {clock_t start = clock();printf("fib_iter(40) = %ld\n", fib_iter(40));clock_t end = clock();printf("Time: %.6f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);start = clock();printf("fib_iter(90) = %ld\n", fib_iter(90));end = clock();printf("Time: %.6f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);return 0;}
The iterative version handles n=90 in three microseconds. The naive recursive version would not finish n=90 before the sun expands into a red giant. The algorithm matters more than the language, the compiler, or the hardware. Always.
Multiple recursion is the right tool for tree and graph traversal, where the branching is structural and each node is visited once. It is the wrong tool when subproblems overlap, as in Fibonacci. In those cases, memoize or iterate. Next: stack overflow errors, the inevitable consequence of unbounded recursion depth.
Finish the lesson once you have worked through the material. This awards ★ 30 XP.