Recursion

Definition

Recursion is a programming technique in which a function calls itself directly or indirectly to solve a problem by reducing it into smaller instances of the same problem until a base condition is reached.

A recursive solution usually contains:

Base case

: The stopping condition that ends recursion.

Recursive case

: The part where the function calls itself with a smaller input.

Example idea:

factorial(5) = 5 × factorial(4)
factorial(4) = 4 × factorial(3)
...
factorial(1) = 1

Here, the problem keeps reducing until it reaches the base case.

Main Content

1. First Concept: Structure of Recursion

Recursion has a clear internal structure that makes it work correctly. Every recursive method should be written with two essential parts: a condition that stops further calls, and a step that moves the problem toward that stopping point.

Base case

The base case is the most important part of recursion because it prevents the function from calling itself forever.
It represents the simplest possible version of the problem, where the answer is already known.
Example: In factorial, factorial(0) = 1 is the base case.

Recursive case

The recursive case is the part where the function solves a smaller version of the same problem by calling itself.
Each recursive call should reduce the problem size so that it eventually reaches the base case.
Example: factorial(n) = n × factorial(n - 1).

A recursive function often looks like this pattern:

function solve(problem):
    if base condition:
        return answer
    else:
        return solve(smaller problem)

If the base case is missing or incorrect, recursion may continue endlessly and cause a stack overflow. If the recursive case does not reduce the problem, the function will never reach the base case.

2. Second Concept: Call Stack and Recursion

Recursion is closely connected to the stack data structure because each function call is placed on the call stack until it finishes. This is one of the most important links between recursion and the unit on stacks and queues.

Function call storage

When a recursive function calls itself, the current state of the function is saved in memory.
This includes local variables, parameters, and the return address.
Each new call is pushed on top of the stack, just like stacking plates.

Unwinding process

When the base case is reached, the function stops calling itself and begins returning results.
The most recent call finishes first, so recursive calls return in reverse order.
This behavior follows the Last In, First Out (LIFO) principle of stacks.

Example: Factorial of 4

factorial(4)
= 4 × factorial(3)
= 4 × (3 × factorial(2))
= 4 × (3 × (2 × factorial(1)))
= 4 × (3 × (2 × 1))
= 24

Stack view for this execution:

Top -> factorial(1)
       factorial(2)
       factorial(3)
Bottom factorial(4)

As each call returns, the stack gets reduced in reverse order. This is why recursion is often described as a "stack-based" process.

Recursive programming can also be simulated using an explicit stack, which is a common technique in iterative solutions for problems normally solved recursively.

3. Third Concept: Types and Uses of Recursion

Recursion can appear in different forms, and understanding these forms helps in writing better algorithms and solving different kinds of problems.

Direct recursion

A function calls itself directly.
Example:

    function f(n):
        if n == 0: return
        f(n - 1)

Indirect recursion

A function calls another function, and that second function eventually calls the first one.
Example: Function A calls B, and B calls A.
This is less common but useful in some special logic and parsing problems.

Tail recursion

The recursive call is the last operation in the function.
Example:

    function countdown(n):
        if n == 0: return
        print(n)
        countdown(n - 1)

Tail recursion can sometimes be optimized by compilers or interpreters.

Common applications

Tree traversal such as preorder, inorder, and postorder.
Searching and backtracking problems.
Mathematical computations like factorial, Fibonacci, GCD.
Divide-and-conquer algorithms like merge sort and quicksort.

Example of recursion in tree traversal:

In inorder traversal, recursion naturally visits: D -> B -> E -> A -> C

This is easier to express recursively than iteratively in many cases.

Working / Process

1. Identify the base case

Determine the simplest input where the answer is already known.
This condition must stop the recursion.
Example: For factorial, the base case is n == 0 or n == 1.

2. Break the problem into a smaller version

Reduce the size of the current problem so that it gets closer to the base case.
Example: factorial(n) becomes n × factorial(n - 1).
This step is what makes recursion progress correctly.

3. Allow the call stack to return results

Once the base case is reached, the function starts returning values back through previous calls.
Each suspended call resumes, uses the returned result, and then finishes.
This return sequence builds the final answer.

Example walkthrough for factorial(3):

factorial(3)
= 3 × factorial(2)
= 3 × (2 × factorial(1))
= 3 × (2 × 1)
= 6

Stack behavior:

Call: factorial(3)
Call: factorial(2)
Call: factorial(1)
Return: 1
Return: 2
Return: 6

This process shows how recursion divides a problem into smaller parts during the call phase and combines results during the return phase.

Advantages / Applications

Simple and elegant code

Recursion often makes code shorter and easier to read, especially for problems that are naturally self-similar.
It matches the mathematical description of many problems very well.
For example, tree traversal is usually more straightforward with recursion.

Useful for complex problem solving

Recursion is effective in divide-and-conquer and backtracking algorithms.
It helps solve problems where each solution depends on smaller subproblems.
Examples include merge sort, quicksort, N-Queens, and maze solving.

Natural fit for hierarchical data

Data structures like trees and graphs often have recursive relationships.
Recursion is ideal for processing such structures because each node may contain smaller substructures of the same type.
It is also used in parsing expressions, directory traversal, and XML/JSON processing.

Summary

Recursion is a method where a function solves a problem by calling itself on smaller inputs.
It works using a base case and a recursive case.
It is closely connected to the call stack and follows stack behavior.

Important terms to remember

Base case
Recursive case
Call stack
Stack overflow
Direct recursion
Indirect recursion
Tail recursion