Select Page

Recursion:

Recursion is a programming technique where a function calls itself to solve a problem. It involves breaking down a problem into smaller subproblems of the same type, solving each subproblem recursively, and combining the results to solve the original problem.

Recursive Definition and Process:

  • Recursive Definition: A recursive definition is one that defines a concept in terms of itself. In programming, recursive functions are defined in terms of themselves, where the function body calls the same function.
  • Recursive Process: When a function calls itself, it creates a chain of function calls, each solving a smaller subproblem. This process continues until a base case is reached, which stops the recursion and allows the function calls to unwind, combining the results to solve the original problem.

Recursion in C:

C language supports recursion like other programming languages. A function in C can call itself, allowing for the implementation of recursive algorithms.

Example of Recursion:

Here’s an example of a recursive function in C to calculate the factorial of a non-negative integer:

c

#include <stdio.h>

// Recursive function to calculate factorial
int factorial(int n) {
// Base case: factorial of 0 is 1
if (n == 0)
return 1;
// Recursive case: n! = n * (n-1)!
else
return n * factorial(n – 1);
}

int main() {
int num = 5;
printf(“Factorial of %d is %d\n”, num, factorial(num));
return 0;
}

In this example, the factorial function calls itself recursively until it reaches the base case (when n == 0). Then, it returns 1, which allows the recursion to unwind, multiplying the returned value by n at each level of recursion.

Tower of Hanoi Problem:

The Tower of Hanoi is a classic problem that can be solved recursively. Given three rods and a number of disks of different sizes stacked in increasing order of size on one of the rods, the objective is to move all the disks from the initial rod to another rod, obeying the following rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the top disk from one stack and placing it on top of another stack.
  3. No disk may be placed on top of a smaller disk.

Simulating Recursion:

Recursion can be simulated using a stack data structure. Instead of making recursive function calls, you can manually manage a stack to store function calls, parameters, and return addresses. This approach is often used in languages or environments that don’t support recursion directly or to optimize tail-recursive functions. However, it’s more complex and less intuitive than direct recursion.