Recursion in Programming

Learn recursion in programming with clear definitions, base and recursive cases, factorial and Fibonacci examples, types of recursion, advantages, and time complexity.

Recursion in Programming

Recursion: Basic Concepts

The Recursion is a programming technique in which a function calls itself to solve a problem. A large problem is divided into smaller subproblems of the same type until a simple condition is reached.

Recursion is widely used in algorithms such as:

• Factorial
• Fibonacci Series
• Tree Traversal
• Tower of Hanoi
• Binary Search

How Does Recursion Work?

In recursion:

1. A function calls itself.
2. The problem size becomes smaller with each call.
3. Eventually, the problem becomes very small.
4. The function stops calling itself.
5. This stopping condition is called the Base Case.
6. After reaching the base case, backtracking starts.
7. The final result is produced while returning from calls.

Two Essential Parts of Recursion

1. Base Case

• The condition that stops further recursive calls.
• Without a base case, recursion will never stop, leading to infinite recursion.

Example (Factorial):

if (n == 0)

    return 1;

2. Recursive Case

• The part where the function calls itself.
• The problem size is reduced in each call.

Example (Factorial):

return n * factorial(n – 1);

Example 1: Recursion – Factorial

Recursive Definition

• factorial(0) = 1 → Base Case
• factorial(n) = n × factorial(n − 1) → Recursive Case

Example Calculation

factorial(4)

= 4 × factorial(3)

= 4 × (3 × factorial(2))

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

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

= 4 × 3 × 2 × 1 × 1

= 24

Example 2: Recursion – Fibonacci Series

Definition

• fibonacci(0) = 0
• fibonacci(1) = 1
• fibonacci(n) = fibonacci(n − 1) + fibonacci(n − 2)

Example

fibonacci(5)

= fibonacci(4) + fibonacci(3)

= 3 + 2

= 5

Types of Recursion

1. Direct Recursion

A function calls itself directly.

fun()

{

    fun();

}

2. Indirect Recursion

One function calls another function, which in turn calls the first function.

A() → B() → A()

3. Tail Recursion

The recursive call is the last statement in the function.

fun(n)

{

    if (n == 0)

        return;

    fun(n – 1);   // last operation

}

4. Head Recursion

The recursive call occurs before other operations.

fun(n)

{

    if (n == 0)

        return;

    fun(n – 1);   // first operation

    print(n);

}

Advantages of Recursion

• Simplifies solutions to complex problems
• Code is short, clean, and readable
• Very effective for tree and graph problems
• Useful in Divide and Conquer algorithms

Disadvantages of Recursion

• Uses more stack memory
• Function call overhead makes it slower
• Risk of infinite recursion if base case is incorrect
• Iterative solutions are often faster and more memory-efficient

When to Use Recursion?

• When a problem can be divided into smaller similar subproblems
• Tree and graph traversal
• Divide and Conquer techniques
• Mathematical problems (Factorial, Fibonacci)

How Recursion Works in Stack Memory

Each recursive call creates a new stack frame containing:

• Local variables
• Function parameters
• Return address

When the base case is reached, the stack starts unwinding, and the final result is produced step by step.

Time Complexity of Recursion

Time complexity depends on the recursive algorithm:

• Factorial → O(n)
• Fibonacci (naive) → O(2ⁿ)
• Binary Search → O(log n)
• Tower of Hanoi → O(2ⁿ − 1)

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1