Skip to main content

Recursive function and how it works

Short answer

A recursive function calls itself with a smaller input until a base case stops recursion. It uses stack memory for each call. Example: factorial (n * factorial(n-1)). Use it when a problem decomposes into similar subproblems.

What is a recursive function? How does it work? Give an example of recursive function. When can we use recursive functions?

Recursive function

A recursive function is a function that calls itself, directly or indirectly, to solve a smaller version of the same problem.

How it works

  • It must have a base case, a condition that stops the recursion; otherwise it never ends.
  • It has a recursive case which calls itself with a smaller (simpler) argument.
  • Each call gets its own set of local variables on the stack. When the base case is reached, the calls return one after another in reverse order, and the results are combined.

Example: factorial

#include <stdio.h>
long factorial(int n)
{
    if (n <= 1)                 /* base case */
        return 1;
    return n * factorial(n - 1);   /* recursive case */
}
int main(void)
{
    int n = 5;
    printf("%d! = %ld\n", n, factorial(n));
    return 0;
}

Output:

5! = 120

factorial(3) = 3 * factorial(2)
                    = 2 * factorial(1)
                          = 1       <- base case
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6

When to use recursion

When a problem can be divided into similar smaller problems: factorial, Fibonacci series, GCD, power, Tower of Hanoi, binary search, tree traversal and sorting methods like quick sort.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Programming chapter 6 questions →