Recursion

Understanding Recursion:

Recursion is a fundamental concept in programming and data structures, where a function calls itself to solve a problem. This technique works under a condition called the base case, which ensures the recursion eventually stops. Recursion is both time-efficient and memory-efficient when used appropriately, especially for problems that can be divided into smaller, identical sub-problems.

In simple terms, recursion allows breaking down complex problems into manageable parts. It is commonly used in algorithms like divide and conquer, tree traversals, and dynamic programming.

Key Points:

• Base Case: The condition at which recursion stops.
• Recursive Step: The step where the function calls itself with a smaller sub-problem.
• Stack Overflow: If the base case is not defined or met, recursion continues indefinitely, causing a stack overflow.

Visualizing Recursion:

Consider a simple example: finding the factorial of a number.

Example: Factorial Calculation

def factorial(n):
 if n == 0:  # Base case
     return 1
 return n * factorial(n - 1)  # Recursive call
print(factorial(5))  # Output: 120

Core Concepts:

Tail Recursion

In tail recursion, the recursive call is the last operation in the function. This allows some compilers or interpreters to optimize the recursive calls and save memory.

function tailFactorial(n, acc = 1) {
 if (n === 0) return acc; // Base case
 return tailFactorial(n - 1, acc * n); // Tail recursion
}
console.log(tailFactorial(5)); // Output: 120

Applications of Recursion

Recursive vs Iterative Approaches

TOH using recursion

Objective: The objective of tower of honoi (TOH) is to transfer all the disks from origin pole to destination pole using intermediate pole for temporary storage.

condition

1. Move Only one disk at a time.
   
2. Each disk must always be placed around one of the pole.
   
3. Never place larger disk on top of smaller disk.
   

Algorithm: Algorithm to move a tower of n disk from source to destination.(where n is positive integer).

step 1: if n == 1:
Move a single disk frome source to destination.
step 2: if n > 1:
i. Let temp be the other pole than source and destination.
ii. Move a tower of (n-1) disk from source to temp.
iii. Move a single disk from source to destination.
iv. Move a tower of (n-1) disk from temp to destination.
step 3: END

Pseudocode

TOH(n, src, dist, temp){
if n == 1:
Display "Move disc {n} from source to destination"
else{
TOH(n-1, src, temp, dist)
Display "Move disc {n} from source to destination"
TOH(n-1, temp, dist, src)
}
}

//toh.cpp
#include <iostream>
using namespace std;
void toh(int n, string src, string dist, string temp)
{
if (n == 1)
{
    cout << "Move disc " << n << "from " << src << " to " << dist << endl;
}
else
{
    toh(n - 1, src, temp, dist);
    cout << "Move disc " << n << "from " << src << " to " << dist << endl;
    toh(n - 1, temp, dist, src);
}
return;
}

int main()
{
int n;
cout << "Enter the number of disc: ";
cin >> n;
toh(n, "Source", "Destination", "Temporary");
return 0;
}

Here's the TOH recursion tree for 4 disks:

Conclusion:

Recursion is a powerful tool in a developer's arsenal. However, it is essential to use it judiciously, keeping efficiency and readability in mind. Explore recursion by solving classic problems like Fibonacci, Tower of Hanoi, and tree traversals!