Module 11: Recursion in C

Learning Objectives

By the end of this module, you will be able to:

• Understand recursion and how it works.
• Write recursive functions in C.
• Learn the importance of the base case.
• Understand recursion trees.
• Differentiate between normal recursion and tail recursion.
• Learn the basics of backtracking.
• Solve classic recursive problems such as Fibonacci, Binary Search, Tower of Hanoi, and Maze Solver.

Introduction

Recursion is one of the most important concepts in programming and forms the foundation of many Data Structures and Algorithms (DSA).

Many advanced algorithms use recursion, including:

• Binary Search
• Merge Sort
• Quick Sort
• Depth First Search (DFS)
• Tree Traversal
• Graph Traversal
• Dynamic Programming
• Divide and Conquer
• Backtracking

Although recursion may seem confusing at first, it becomes much easier once you understand how function calls are stored in memory.

What is Recursion?

Recursion is a programming technique in which a function calls itself to solve a smaller version of the same problem.

Instead of solving the entire problem at once, recursion divides it into smaller subproblems until a stopping condition is reached.

Example

Suppose you want to calculate:

textCopy
15!

Instead of writing:

textCopy
15 × 4 × 3 × 2 × 1

A recursive solution thinks like this:

textCopy
15!
2
3↓
4
55 × 4!
6
7↓
8
95 × 4 × 3!
10
11↓
12
135 × 4 × 3 × 2!
14
15↓
16
175 × 4 × 3 × 2 × 1!
18
19↓
20
215 × 4 × 3 × 2 × 1

How Recursion Works

Every recursive function creates a new function call.

Each function call is stored in the Call Stack.

Example

cCopy
1factorial(3)

Execution

textCopy
1factorial(3)
2
3↓
4
5factorial(2)
6
7↓
8
9factorial(1)
10
11↓
12
13factorial(0)
14
15↓
16
17Return

The stack grows until the base case is reached.

Recursive Function

A recursive function is simply a function that calls itself.

Example

cCopy
1#include <stdio.h>
2
3void countdown(int n)
4{
5    if(n == 0)
6        return;
7
8    printf("%d\n", n);
9
10    countdown(n - 1);
11}
12
13int main()
14{
15    countdown(5);
16
17    return 0;
18}

Output

textCopy
15
24
33
42
51

Base Case

Every recursive function must have a base case.

The base case tells the function when to stop calling itself.

Without a base case, recursion never ends.

Correct Example

cCopy
1int factorial(int n)
2{
3    if(n == 0)
4        return 1;
5
6    return n * factorial(n - 1);
7}

The base case is:

cCopy
1if(n == 0)
2    return 1;

Incorrect Example

cCopy
1int factorial(int n)
2{
3    return n * factorial(n - 1);
4}

This function never stops.

Eventually, the program crashes with a Stack Overflow error.

Recursive Tree

A recursion tree helps visualize how recursive calls are made.

Example:

textCopy
1fibonacci(5)

Recursion Tree

textCopy
1                    fib(5)
2                  /        \
3             fib(4)        fib(3)
4            /     \        /     \
5        fib(3) fib(2) fib(2) fib(1)
6        /   \     |
7    fib(2) fib(1) fib(1)
8      |
9   fib(1)

Notice that many subproblems are solved repeatedly.

This is why the recursive Fibonacci algorithm is inefficient.

Recursive Factorial

Formula

textCopy
1n! = n × (n-1)!

Program

cCopy
1#include <stdio.h>
2
3int factorial(int n)
4{
5    if(n <= 1)
6        return 1;
7
8    return n * factorial(n - 1);
9}
10
11int main()
12{
13    int number;
14
15    printf("Enter a number: ");
16    scanf("%d", &number);
17
18    printf("Factorial = %d", factorial(number));
19
20    return 0;
21}

Output

textCopy
1Enter a number: 5
2
3Factorial = 120

Recursive Fibonacci

Formula

textCopy
1F(n)=F(n−1)+F(n−2)

Program

cCopy
1#include <stdio.h>
2
3int fibonacci(int n)
4{
5    if(n <= 1)
6        return n;
7
8    return fibonacci(n - 1) + fibonacci(n - 2);
9}
10
11int main()
12{
13    int n;
14
15    printf("Enter position: ");
16    scanf("%d", &n);
17
18    printf("%d", fibonacci(n));
19
20    return 0;
21}

Output

textCopy
1Enter position: 7
2
313

Time Complexity

textCopy
1O(2ⁿ)

Tail Recursion

A recursive function is tail recursive if the recursive call is the last operation performed.

Example

cCopy
1#include <stdio.h>
2
3void countdown(int n)
4{
5    if(n == 0)
6        return;
7
8    printf("%d\n", n);
9
10    countdown(n - 1);
11}

Since nothing happens after the recursive call, it is tail recursion.

Non-Tail Recursion

cCopy
1int factorial(int n)
2{
3    if(n == 0)
4        return 1;
5
6    return n * factorial(n - 1);
7}

Multiplication occurs after the recursive call returns.

Therefore, this is not tail recursion.

Tail Recursive Factorial

cCopy
1#include <stdio.h>
2
3int factorialTail(int n, int result)
4{
5    if(n <= 1)
6        return result;
7
8    return factorialTail(n - 1, n * result);
9}
10
11int main()
12{
13    printf("%d", factorialTail(5, 1));
14
15    return 0;
16}

Output

textCopy
1120

Some compilers can optimize tail-recursive functions to reduce stack usage, but this optimization is not guaranteed.

Advantages of Recursion

• Cleaner code
• Easier implementation for divide-and-conquer algorithms
• Natural solution for trees and graphs
• Simplifies many mathematical problems
• Useful for backtracking algorithms

Disadvantages of Recursion

• More memory usage due to the call stack
• Can cause stack overflow
• Often slower than iterative solutions
• Some recursive algorithms repeat the same calculations

Backtracking Basics

Backtracking is an advanced recursive technique.

It works by:

1. Choose a possible solution.
2. Continue recursively.
3. If the solution fails, undo the last choice.
4. Try another option.

This process is often called:

textCopy
1Choose
2
3↓
4
5Explore
6
7↓
8
9Backtrack
10
11↓
12
13Try Again

Applications:

• Sudoku Solver
• N-Queens Problem
• Maze Solver
• Rat in a Maze
• Crossword Solver
• Permutations
• Combinations

Practice Project 1: Tower of Hanoi

Problem:

Move all disks from Source to Destination using an Auxiliary rod.

Rules:

• Move one disk at a time.
• A larger disk cannot be placed on a smaller disk.
• Use the auxiliary rod when needed.

Program

cCopy
1#include <stdio.h>
2
3void towerOfHanoi(int n, char source, char auxiliary, char destination)
4{
5    if(n == 1)
6    {
7        printf("Move Disk 1 from %c to %c\n", source, destination);
8        return;
9    }
10
11    towerOfHanoi(n - 1, source, destination, auxiliary);
12
13    printf("Move Disk %d from %c to %c\n", n, source, destination);
14
15    towerOfHanoi(n - 1, auxiliary, source, destination);
16}
17
18int main()
19{
20    towerOfHanoi(3, 'A', 'B', 'C');
21
22    return 0;
23}

Time Complexity

textCopy
1O(2ⁿ)

Practice Project 2: Recursive Binary Search

Binary Search works only on a sorted array.

cCopy
1#include <stdio.h>
2
3int binarySearch(int arr[], int left, int right, int target)
4{
5    if(left > right)
6        return -1;
7
8    int mid = left + (right - left) / 2;
9
10    if(arr[mid] == target)
11        return mid;
12
13    if(target < arr[mid])
14        return binarySearch(arr, left, mid - 1, target);
15
16    return binarySearch(arr, mid + 1, right, target);
17}
18
19int main()
20{
21    int arr[] = {2, 5, 8, 12, 16, 23, 38};
22    int size = sizeof(arr) / sizeof(arr[0]);
23    int target = 16;
24
25    int index = binarySearch(arr, 0, size - 1, target);
26
27    if(index != -1)
28        printf("Element found at index %d", index);
29    else
30        printf("Element not found");
31
32    return 0;
33}

Time Complexity

textCopy
1O(log n)

Practice Project 3: Maze Solver (Backtracking)

The following program finds a path in a maze using recursion and backtracking.

cCopy
1#include <stdio.h>
2
3#define N 4
4
5int maze[N][N] =
6{
7    {1,0,0,0},
8    {1,1,0,1},
9    {0,1,0,0},
10    {1,1,1,1}
11};
12
13int solution[N][N];
14
15int solveMaze(int x, int y)
16{
17    if(x == N - 1 && y == N - 1)
18    {
19        solution[x][y] = 1;
20        return 1;
21    }
22
23    if(x >= 0 && x < N && y >= 0 && y < N &&
24       maze[x][y] == 1 && solution[x][y] == 0)
25    {
26        solution[x][y] = 1;
27
28        if(solveMaze(x + 1, y))
29            return 1;
30
31        if(solveMaze(x, y + 1))
32            return 1;
33
34        solution[x][y] = 0;
35    }
36
37    return 0;
38}
39
40int main()
41{
42    if(solveMaze(0, 0))
43    {
44        printf("Solution Path:\n");
45
46        for(int i = 0; i < N; i++)
47        {
48            for(int j = 0; j < N; j++)
49            {
50                printf("%d ", solution[i][j]);
51            }
52            printf("\n");
53        }
54    }
55    else
56    {
57        printf("No Solution Found");
58    }
59
60    return 0;
61}

Output

textCopy
1Solution Path:
21 0 0 0
31 1 0 0
40 1 0 0
50 1 1 1

Dry Run Example

Recursive call:

textCopy
1factorial(4)

Execution

textCopy
1factorial(4)
2
3↓
4
5factorial(3)
6
7↓
8
9factorial(2)
10
11↓
12
13factorial(1)
14
15↓
16
17Return 1
18
19↓
20
21Return 2
22
23↓
24
25Return 6
26
27↓
28
29Return 24

Common Mistakes to Avoid

• Forgetting the base case.
• Writing a base case that is never reached.
• Modifying variables incorrectly before the recursive call.
• Ignoring stack overflow for deep recursion.
• Using recursion where an iterative solution is simpler.
• Recomputing the same values repeatedly, as in the naive Fibonacci algorithm.

Best Practices

• Always define a clear and reachable base case.
• Ensure each recursive call moves closer to the base case.
• Test recursive functions with small inputs first.
• Use recursion for naturally recursive problems such as trees, divide-and-conquer, and backtracking.
• Prefer iterative solutions when recursion may cause excessive stack usage.
• Consider memoization or dynamic programming to optimize recursive algorithms with overlapping subproblems.

Module Summary

In this module, you learned:

• What recursion is and how recursive functions work.
• Why the base case is essential to stop recursion.
• How recursion uses the call stack.
• How recursion trees visualize recursive calls.
• The difference between tail recursion and non-tail recursion.
• The basics of backtracking and its applications.
• How to solve classic recursive problems such as Factorial, Fibonacci, Binary Search, Tower of Hanoi, and a Maze Solver.

After completing this module, you'll be ready to learn Searching Algorithms, including Linear Search, Binary Search, interpolation search, and techniques for analyzing and optimizing search performance using Big O notation.