Activity: Recursion

Brief Intro — Recursion

Recursion is a programming technique where a function solves a problem by calling itself with a smaller version of the same problem. It allows for elegant solutions to complex mathematical challenges, like factorials and Fibonacci sequences.

In this activity, you'll explore how recursion works, why every recursive function needs a base case, and how the computer uses a stack to keep track of nested calls.

Task 1: Definition of Recursion

Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.

Task 2: Self-Calling Code

Trace the classic self-calling snippet from the notes:

void recursion() {
    recursion();   /* function calls itself */
}

int main() {
    recursion();
    return 0;
}

Here recursion() calls itself from inside its own body. Without any stopping condition this call would repeat forever.

Task 3: The Exit Condition

C supports recursion, i.e., a function that calls itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.

Task 4: What Recursion Is Good For

Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number and generating the Fibonacci series.

Task 5: Code Anatomy

The notes' recursive factorial function:

unsigned long long int factorial(unsigned int i) {
    if(i <= 1) {
        return 1;
    }
    return i * factorial(i - 1);
}

Two parts: a base case (i <= 1 returns 1) and a recursive step (i * factorial(i - 1)).

Task 6: The Base Case

When i <= 1, the function returns 1. This is the exit condition in action: it stops the chain of calls so the function does not loop forever.

Task 7: The Recursive Step

The line return i * factorial(i - 1); builds the chain. Each call multiplies i by the result of the next, smaller call.

Task 8: Output Trace

In main(), int i = 12; then printf("Factorial of %d is %d\n", i, factorial(i)); prints:

Factorial of 12 is 479001600

Use the Stack Visualizer above to watch the smaller case factorial(5) — push frames 5, 4, 3, 2, 1, hit the base case, then unwind 1 → 1 → 2 → 6 → 24 → 120.

▶ Try it: Base Case ▶ Try it: Full Trace

Task 9: The Advantage

Recursion makes programs elegant. Recursive solutions are often shorter and mirror the mathematics of the problem directly.

Task 10: The Disadvantage

If performance is vital, use loops instead, because recursion is usually much slower. Every call has overhead — a new frame is pushed and the return value must unwind.

Task 11: Where Recursion Is Used

Recursion is an important concept, frequently used in data structures and algorithms. For example, it is common to use recursion in problems such as tree traversal.

Task 12: Loop vs Recursion Trade-off

For each scenario, decide whether the notes recommend recursion or a loop:

• You want the code to be elegant → use recursion.
• Performance is vital → use a loop.
• You are doing tree traversal → recursion is the natural choice.