Recursion

Recursion is a programming technique in which a function directly or indirectly calls itself during its definition or execution. The core idea is to decompose a complex problem into smaller subproblems of the same structure.

Basic Concepts of Recursion

Recursive call stack frame changes — using factorial(3) as an example

fact(3)Waiting for fact(2) to return → push stack

↓ call

fact(2)Waiting for fact(1) to return → push stack

↓ call

fact(1)Waiting for fact(0) to return → push stack

↓ call

fact(0) = 1Base condition! Begin returning → pop stack

↑ Return layer by layer (LIFO)

fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 3 × 2 × 1 × 1 = 6

Orange box (base condition) → stop recursion and start returning | Stack frames are popped in LIFO order: the last one pushed is the first to return

A valid recursive function must contain two key elements:

Element	Meaning	Example (Factorial)
Base condition	The condition for terminating recursion, preventing infinite recursion.	`if (n == 0) return 1;`
Recursive condition	Decompose the problem into smaller subproblems and call itself.	`return n * factorial(n-1);`

Classic Recursion Problems

Factorial

Example

#include <stdio.h>

/* Factorial recursive implementation
n! = n × (n-1)!, base condition: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* Base condition */
return n * factorial(n - 1); /* Recursive condition */
}

int main() {
printf("5! = %lld\n", factorial(5)); /* Output: 120 */
return 0;
}

Fibonacci Sequence

Example

#include <stdio.h>

/* Naive recursion: a lot of repeated computation, O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* Base condition */
return fib(n-1) + fib(n-2); /* Recursive condition */
}

/* Memoization optimization: cache computed results, O(n) */
#define MAX 100
long long memo[MAX] = {0};

long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* Already computed, return directly */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}

int main() {
printf("fib(10) (naive): %d\n", fib(10)); /* Output: 55 */
printf("fibMemo(50) (memoized): %lld\n", fibMemo(50)); /* Output: 12586269025 */
return 0;
}

Tower of Hanoi Problem

Example

#include <stdio.h>

/* Tower of Hanoi recursive solution
Move n disks from src to dst with the help of aux
Steps: move n-1 from src→aux, the largest from src→dst, n-1 from aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* Move n-1 disks from src to aux */
printf("Move disk %d from %c to %c\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* Move n-1 disks from aux to dst */
}

int main() {
printf("Tower of Hanoi (3 disks):\n");
hanoi(3, 'A', 'B', 'C');
/* Output: 7 steps in total (2³-1), minimum steps = 2ⁿ-1 */
return 0;
}

Recursion vs Iteration

Dimension	Recursion	Iteration
Code readability	High(Close to mathematical definition)	Sometimes not as intuitive as recursion
Execution efficiency	Lower(Stack frame overhead)	Higher
Space overhead	O(recursion depth) stack space	O(1)
Stack overflow risk	Yes(When depth is too large)	None
Applicable structures	Natural recursive structures like trees and graphs	Linear structures such as arrays

Tail recursionIt is a special form of recursion in which the recursive call is the last operation executed in the function body. Some compilers can optimize tail recursion by converting it into equivalent iteration to save stack space. However, not all C compilers enable this optimization by default.

Other extensions