Recursion is a programming technique in which a function calls itself to solve a problem by breaking it down into smaller and simpler subproblems.

Instead of solving the entire problem at once, recursion focuses on solving a reduced version of the problem repeatedly until a stopping condition is reached.

What Is Recursion?

In recursion, a function solves a problem by calling itself with a smaller input.

Each recursive call works on a reduced version of the original problem until it reaches a point where no further calls are needed.

Recursion is commonly used in problems that naturally break down into similar subproblems.

Key Components of Recursion

Base Case

The base case is the condition that stops the recursion.

Without a base case, recursion will continue indefinitely and eventually cause a stack overflow error.

The base case represents the simplest version of the problem.

Recursive Case

The recursive case is the part of the function where it calls itself.

Each recursive call must move closer to the base case by reducing the input size.

How Recursion Works Internally

When a recursive function is called:

  • The function call is placed on the call stack
  • Each recursive call gets its own stack frame
  • Local variables are stored separately for each call
  • Once the base case is reached, functions start returning values in reverse order

This process is known as stack unwinding.

Example: Factorial Using Recursion

The factorial of a number is calculated by multiplying the number with the factorial of the number minus one.

Execution for factorial of 3:

  • factorial(3) becomes 3 multiplied by factorial(2)
  • factorial(2) becomes 2 multiplied by factorial(1)
  • factorial(1) becomes 1 multiplied by factorial(0)
  • factorial(0) returns 1

Once the base case is reached, the values return back step by step.

Time and Space Complexity

For the factorial problem:

Time complexity is O(n) because the function is called n times.

Space complexity is O(n) because each recursive call occupies space on the call stack.

Types of Recursion

Direct Recursion

The function calls itself directly within its own body.

Indirect Recursion

The function calls another function, which eventually calls the original function again.

Tail Recursion

The recursive call is the last operation performed in the function.

No additional computation is done after the recursive call returns.

Non-Tail Recursion

The recursive call is followed by additional operations.

Most common recursive problems fall into this category.

Advantages of Recursion

  • Simplifies complex problems
  • Produces cleaner and more readable code for divide-and-conquer problems
  • Very useful for tree and graph traversal
  • Matches the natural structure of many problems

Disadvantages of Recursion

  • Uses extra memory due to the call stack
  • Can cause stack overflow if the base case is missing or incorrect
  • Sometimes slower than iterative solutions

When to Use Recursion

Recursion should be used when:

  • The problem can be divided into similar subproblems
  • Tree, graph, or divide-and-conquer problems are involved
  • Code clarity is more important than performance

Conclusion

Recursion is a powerful problem-solving technique when used correctly.

Understanding base cases, recursive cases, and call stack behavior is essential for mastering recursion.

A strong grasp of recursion is fundamental for advanced topics such as trees, graphs, backtracking, and dynamic programming.