Recursive function

📖 Theory

The function that phones itself

Every function so far called OTHERS. C permits something stranger: a function calling itself.

First reaction, rightly: "that must loop forever."

Almost. With one missing ingredient it truly is an infinite hall of mirrors, and with that ingredient it becomes the most elegant four lines in this subject: factorial, computed by a function that trusts a smaller copy of itself to do most of the work.

📖 Theory

Asking down the queue

You are last in a long queue and need to know your position. Ask the person AHEAD: "what is your position?" They do not know either, so they ask ahead... until the question reaches the FIRST person, who simply KNOWS: "I am number 1" (the base case). Now answers flow backward, each person adding one, until yours arrives. One question passed down, answers built up: that is recursion's entire machinery.

📖 Theory

Recursion, formally

A recursive function needs exactly two parts:

• Base case: the smallest input, answered DIRECTLY, no further calls. It is the brake.
• Recursive case: the problem restated via a smaller self.

Factorial (n! = n × (n-1) × ... × 1) restates naturally: n! = n × (n-1)! and 0! = 1:

int factorial(int n) {

if (n == 0) return 1; /* base case */

return n * factorial(n - 1); /* smaller self */

}

Every call must move TOWARD the base case, smaller n each time, or the brake is never reached.

⌨️ Practical

Factorial, recursive and looped

#include <stdio.h>

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

int main() {
    int f = 1, i, n = 4;
    printf("Recursive: %d\n", factorial(4));

    for (i = 1; i <= n; i++) f = f * i;   /* the loop twin */
    printf("Loop     : %d\n", f);
    return 0;
}

This example runs in Gri-Learn on the web, where you can edit it and see the output.

💭 Think first

Trace the stack

Trace factorial(4) on paper: write the chain of calls going DOWN, mark where it stops, then multiply the results coming back UP. What returns, and which data structure held the paused calls?

🧩 Quiz

A student deletes the base case: int factorial(int n) { return n * factorial(n - 1); } and calls factorial(4). What happens?

1. Calls never stop; the call stack overflows and the program crashes
2. It returns 24 anyway, C knows factorials
3. A compile error: base cases are mandatory syntax
4. It returns 0 immediately

🧩 Quiz

Factorial works as a loop AND as recursion. Which statement compares them correctly?

1. Both are correct; the loop avoids stacked calls, recursion shines on naturally nested problems
2. Recursion is always faster than loops
3. Loops cannot compute factorials above 3
4. Recursion never uses extra memory

⚠️ Watch out

Where marks leak

No base case, or one the calls never reach (factorial(n-1) with a base of n == 5 called on 4): both end in stack overflow, check the direction of shrinking. Wrong base value: factorial(0) must return 1, not 0, one wrong brake and every answer above it is 0. Tracing sloppily: exams want the down-chain AND the up-multiplication written out; skipping the return journey costs half the marks.

📖 Theory

The classic second example

Fibonacci (each number the sum of the previous two: 0 1 1 2 3 5 8...) is recursion's other exam star: fib(n) = fib(n-1) + fib(n-2), with TWO base cases (fib(0)=0, fib(1)=1). Write it tonight; trace fib(4). One lesson remains in C: the struct, where our student finally gets name, marks and grade in ONE record, the payoff of the entire subject.

✅ Summary

Key takeaways

• Recursion: a function calling itself on a SMALLER input.
• Two mandatory parts: base case (the brake) + recursive case (smaller self).
• factorial: if (n == 0) return 1; return n * factorial(n - 1);
• Paused calls wait on the call stack (LIFO); results multiply on the way back.
• No base case → stack overflow crash; base must be reachable and correct.
• Loops for straight counts; recursion for naturally nested problems.
• Memory hook: ask down the queue, answers come back up.