Recursion

Dr. Preeti Mittal

IIMT University
Recursion
Recursion is a programming technique where a function calls itself within its body.
It allows us to break down complex problems into smaller, self-similar subproblems that
can be solved using the same function.
Principles of Recursion
The key principles of recursion:

1. Base Case: This is a simple condition that can be solved directly without further
function calls. It acts as the termination point for the recursion.
2. Recursive Case: This part of the function breaks down the larger problem into a
smaller, self-similar subproblem. It then calls itself with the smaller problem as an
argument.
3. Return Statement: Each recursive call must eventually lead to a return statement,
either from the base case or from a deeper recursive call.
Example
int factorial(int n)
{
This function calculates the factorial of a number (n!).
if (n == 0) // Base case
{ In the base case, if n is 0, the factorial is 1.
return 1;
For the recursive case, the function calls itself with n-1 as
}
the argument and multiplies the result with n.
else
{ // Recursive case This process continues until the base case is reached.
return n * factorial(n - 1);
}
}
Tail Recursion:
● Tail recursion is a specific type of recursion where the recursive call is the last
statement in the function body.
● This allows the compiler to optimize the function call and avoid creating unnecessary
stack frames, improving efficiency.
● Tail recursion can be identified :
1. The function call is the last statement in the function body.
2. The function does not perform any operations after the recursive call (e.g.,
printing a value, modifying a variable).
Removing Recursion and Implementing Iterative Solutions
● Before directly converting from recursion to iteration, it's crucial to understand the problem being solved and
the purpose of the recursive function.
● Grasp the logic behind the recursive calls and the relationship between the function arguments and the desired
output.
● General Steps for Iterative Conversion:
1. Identify the base case: This will be the condition that terminates the iterative loop and directly returns
the result.
2. Initialize variables: Set up any necessary variables to store intermediate results or track the loop's
progress.
3. Create a loop: Based on the structure of the recursive calls, choose an appropriate loop (e.g., while, for)
to iterate until the base case is reached.
4. Simulate recursive calls: Within the loop, use the current loop iteration and the stored variables to
mimic the computations performed during the recursive calls. This might involve updating variables,
performing calculations, and potentially making further iterations within the loop.
5. Return the final result: After the loop has finished iterating and reaching the base case condition,
return the final result calculated or accumulated during the loop iterations.
Example
int factorial(int n) { int factorial(int n) {

if (n == 0) { int result = 1;

if (n == 0) {
return 1;
return 1;
} else {
}
return n * factorial(n - 1);
for (int i = 1; i <= n; ++i) {
}
result *= i; // Simulate multiplication from recursive calls
}
}

return result;

}
Benefits of Iterative Solutions:
● Tail recursion optimization: In some cases, the iterative approach avoids the
overhead associated with function calls, potentially improving performance,
especially for deep recursion.
● Memory efficiency: Iterative solutions typically use less memory compared to
recursion, which can create stack frames for each recursive call.
● Easier to understand and maintain: For some problems, iterative approaches
might be more intuitive and easier to reason about, especially for programmers
less familiar with recursion.
 int fibonacci(int n) {

Fibonacci numbers
if (n <= 1) {

return n; }

else {
● Base Case: If n is less than or equal to 1 (0
or 1), the function directly returns n. These return fibonacci(n - 1) + fibonacci(n - 2);
are the first two terms of the Fibonacci }}
sequence (0 and 1). void main() {
● Recursive Case: If n is greater than 1, the
int num;
function makes two recursive calls:
○ fibonacci(n - 1): This calculates the printf("Enter the number of terms: ");
(n-1)th term of the sequence. scanf("%d", &num);
○ fibonacci(n - 2): This calculates the
printf("Fibonacci Series: ");
(n-2)th term of the sequence.
for (int i = 0; i < num; ++i) {

printf("%d \t ", fibonacci(i));

}}
Hanoi towers
The Tower of Hanoi is a mathematical puzzle involving
three rods and a number of disks of varying sizes. The
objective is to move all the disks from one rod (the
source) to another rod (the destination) while adhering
to specific rules:

Rules:

1. Only one disk can be moved at a time.

2. A larger disk cannot be placed on top of a smaller
disk.
3. Only the top disk on a rod can be moved.
The puzzle can be solved with any number of disks, but
the number of moves required increases exponentially
with the number of disks.
The minimum number of moves required to solve the
Tower of Hanoi puzzle with n disks is 2^n - 1.
Solution
Initial State: All disks, starting with the largest at the bottom, are stacked on the source rod in decreasing
order of size.

Solving the Puzzle: The puzzle can be solved by following a specific set of steps that involve utilizing the
third rod (the auxiliary) as a temporary holder.

Recursive Approach: A common solution involves a recursive function that breaks down the problem into
smaller subproblems. The function recursively moves the disks from the source rod to the destination rod,
using the auxiliary rod as a temporary holder.

Iterative Approach: An alternative method involves building an iterative solution that uses loops and
conditional statements to achieve the same goal of moving all disks while adhering to the rules.
Solution using stack and recursion
1. Stacks: ● Base Case: If n == 1 (only one disk), directly
move it from source to destination.
● We represent each rod as a stack data structure. ● Recursive Case: For n > 1:
● Each element in the stack represents a disk, with
1. Move the top n-1 disks from source to
the larger disks having lower values.
auxiliary, using the destination as
2. Recursive Approach: the temporary rod (recursive call with n-1,
source, destination, and
● The solution involves a recursive function auxiliary).
hanoi(n, source, auxiliary, 2. Move the largest disk from source to
destination), where: destination.
1. n: number of disks
3. Move the n-1 disks from auxiliary to
2. source: source rod
3. auxiliary: auxiliary rod (used for destination, using the source as the
temporary storage) temporary rod (recursive call with n-1,
4. destination: destination rod auxiliary, source, and
destination).
function hanoi(n, source, auxiliary, destination) {
if (n == 1) {
// Base case: move the only disk function move(source, destination) {
move(source, destination); // Implement logic to move the top disk from
} else { source to destination stack
// Recursive case }
hanoi(n - 1, source, destination, auxiliary);
move(source, destination);
hanoi(n - 1, auxiliary, source, destination);
}
}
Thank You