Articles / DSA · Part 20

Recursion: Understanding the Basics

Understand recursion, base cases, recursive calls, and the call stack. Learn how to trace recursive functions and calculate factorial using simple C examples.

Recursion: Understanding the Basics

So far, we’ve learned algorithms that solve problems using loops, comparisons, and data structures.

But what if a function could solve a problem by calling itself?

This idea is called Recursion.

Recursion is an important concept in DSA because it helps solve problems by breaking them into smaller versions of the same problem.

1. What Is Recursion?

Recursion is a programming technique in which a function calls itself to solve a problem.

Instead of solving the entire problem at once, the function handles a smaller part of it and calls itself with a simpler input.

Let’s understand this with a simple example.

Imagine counting backwards from 5 to 1:

5
4
3
2
1

We can write a recursive function that prints a number and then calls itself with the previous number.

C Implementation:

#include <stdio.h>

void countdown(int n) {
    if (n == 0)
        return;

    printf("%d\n", n);

    countdown(n - 1);
}

int main() {
    countdown(5);
    return 0;
}

Output:

5
4
3
2
1

Notice that countdown() calls itself with n - 1.

Each call receives a smaller number until it reaches 0.

But how does the function know when to stop?

That’s where the Base Case comes in.

2. Two Important Parts of Recursion

Every properly designed recursive function needs two important parts.

A. Base Case

A Base Case is the condition that stops the recursive calls.

In our previous example:

if (n == 0)
    return;

When n becomes 0, the function returns without calling itself again.

Without a Base Case, the function may continue calling itself until the program runs out of available stack memory.

This can cause an error called <abbr title=”An error that occurs when recursive or nested function calls use more stack memory than is available.”>Stack Overflow</abbr>.

B. Recursive Case

The Recursive Case is the part where a function calls itself with a smaller or simpler input.

In our example:

countdown(n - 1);

Each call reduces n by one, bringing the function closer to the Base Case.

Remember:

  • Base Case → Stops the recursion.
  • Recursive Case → Calls the function again with a simpler problem.

3. Understanding How Recursion Works

Let’s understand what happens when we call:

countdown(3);

The function calls itself as follows:

Step 1: Function Calls

countdown(3)
      ↓
countdown(2)
      ↓
countdown(1)
      ↓
countdown(0)

When countdown(0) is reached, the Base Case is satisfied. No further calls are made.

Step 2: Returning from Function Calls

After reaching the Base Case, the functions finish and return one by one.

countdown(0) → returns
countdown(1) → returns
countdown(2) → returns
countdown(3) → returns

This happens because each function call waits for the function it called to finish before continuing.

What Is a Call Stack?

Whenever a function is called, the computer keeps track of that function’s information, including its parameters and where it should continue after the function returns.

This information is managed using a <abbr title=”A memory structure that stores information about active function calls. The most recently called function finishes first.”>Call Stack</abbr>.

In recursion, each new call is placed on the stack. When a function finishes, its information is removed from the stack.

This is why recursive calls move downward until the Base Case is reached, and then return upward.

4. A Practical Example: Factorial Using Recursion

Let’s understand a more useful example.

The factorial of a positive integer is the product of all positive integers from that number down to 1.

It is represented using the symbol !.

For example:

There are 5 nodes and 4 edges.

Therefore, the relationship is:

\[
\text{Number of edges} = n – 1
\]

For our example:

\[
5 – 1 = 4
\]

This rule applies to every non-empty tree.

So, each factorial can be calculated using a smaller factorial.

C Implementation

#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;

    return n * factorial(n - 1);
}

int main() {
    int result = factorial(5);

    printf("Factorial = %d", result);

    return 0;
}

Output:

Factorial = 120

Dry Run: factorial(5)

Let’s follow the function calls:

Step 1: Going Down

factorial(5)
    = 5 * factorial(4)

factorial(4)
    = 4 * factorial(3)

factorial(3)
    = 3 * factorial(2)

factorial(2)
    = 2 * factorial(1)

factorial(1)
    = 1

We have reached the Base Case.

Step 2: Returning Up

Now the answers are calculated as the functions return:

factorial(1) = 1

factorial(2) = 2 * 1 = 2

factorial(3) = 3 * 2 = 6

factorial(4) = 4 * 6 = 24

factorial(5) = 5 * 24 = 120

Therefore:

5! = 120

This is how recursion works: the function calls itself until it reaches the Base Case, and then the results are calculated as the calls return.

5. Recursion vs. Iteration

Recursion is not the only way to repeat an operation. We can also use loops such as for and while.

Repeating a process using loops is called <abbr title=”Repeating instructions using loops such as for and while.”>Iteration</abbr>.

Let’s compare both approaches using the same factorial problem.

Feature Recursion Iteration
Approach Function calls itself Uses loops
Stopping condition Base Case Loop condition
Memory Uses call stack for function calls Usually requires less additional memory
Code Can be shorter for some problems Often simpler for repetitive tasks
Risk Stack Overflow with excessive recursion Infinite loop if the condition never becomes false

Both approaches can solve the same problem, but their suitability depends on the problem.

6. Applications of Recursion

Recursion is useful in many areas of computer science.

  • Tree Traversal: Visiting elements of a tree structure.
  • Merge Sort: Dividing an array into smaller parts before sorting them.
  • Quick Sort: Dividing elements around a selected pivot.
  • Graph Traversal: Exploring connected elements using Depth-First Search.
  • Factorial Calculation: Solving mathematical problems through smaller calculations.

We’ll explore these applications in later articles.

Conclusion

Recursion allows a function to call itself to solve a problem through smaller versions of the same problem.

The two essential parts are:

  • Base Case: The condition that stops further calls.
  • Recursive Case: The part that calls the function again with a simpler input.

We also learned how the Call Stack manages recursive calls and how factorial can be calculated using recursion.

The key idea is simple: Break a problem into smaller versions of itself until you reach a condition that can be solved directly.

In the next article, we’ll explore Trees: Definitions, Terminologies, and Properties, one of the most important non-linear data structures in DSA.


Further reading: Harvard CS50 – Recursion · GeeksforGeeks – Recursion

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DSA · Part 1

What is DSA?

Learn DSA from the basics with this beginner-friendly guide to data structures and algorithms. Understand arrays, linked lists, stacks, queues, trees, graphs,…

8 min read

Ask Farhan

Ask anything about Farhan