C Recursion

What Is Recursion?

A recursive function is simply a function that calls itself. Instead of using a loop to repeat work, the function keeps calling itself with a smaller or simpler input until it reaches a point where it can stop. That stopping point is very important, and we will talk about it in a moment.

Here is a classic example: adding up all the numbers from a value down to 1. Each call handles one number, then asks a smaller copy of itself to handle the rest.

#include <stdio.h>

int sum(int k) {
  if (k > 0) {
    return k + sum(k - 1);  // function calls itself
  } else {
    return 0;               // stop here
  }
}

int main() {
  int result = sum(5);
  printf("Sum = %d\n", result);  // 5+4+3+2+1 = 15
  return 0;
}

When you run this program, the output is:

Sum = 15

The Base Case and the Recursive Case

Every safe recursive function has two parts. The base case is the condition that stops the recursion, and the recursive case is where the function calls itself with a smaller problem. Without a base case, the function would call itself forever and eventually crash the program.

• Base case: the simplest input, where the answer is known directly and no further calls are made.
• Recursive case: the function reduces the problem and calls itself again.
• Progress: each call must move closer to the base case, or the recursion never ends.

Factorial: A Classic Example

The factorial of a number n (written n!) is the product of all whole numbers from 1 up to n. For example, 4! = 4 x 3 x 2 x 1 = 24. This is a natural fit for recursion because n! equals n times (n-1)!.

#include <stdio.h>

int factorial(int n) {
  if (n <= 1) {
    return 1;                    // base case
  }
  return n * factorial(n - 1);   // recursive case
}

int main() {
  printf("4! = %d\n", factorial(4));
  printf("6! = %d\n", factorial(6));
  return 0;
}

The output shows both results:

4! = 24
6! = 720

Recursion vs. Loops

Anything you can do with recursion can also be done with a loop, and vice versa. Recursion often produces shorter, cleaner code for problems that are naturally repetitive, but loops usually use less memory because they do not create a new function call each time.