Recursive algorithm refers to a process in which a function calls itself repeatedly until it reaches a base condition. It is a programming technique that allows a function to call itself repeatedly, with each subsequent call solving a smaller version of the original problem. In other words, recursion is a way to solve a problem by breaking it down into smaller subproblems and solving each subproblem in the same way until we reach the base case.
One of the best ways to understand recursion is through real-life examples.
Consider the following scenario: You are standing at the base of a staircase, and you want to reach the top. However, you can only take one or two steps at a time. How many different ways can you reach the top of the staircase?
This problem can be solved using a Recursive Algorithm. We can break down the problem into smaller subproblems by considering the number of steps we can take at each turn. Suppose we take one step, then we need to find the number of ways to reach the top from the remaining (n-1) steps. Similarly, if we take two steps, we need to find the number of ways to reach the top from the remaining (n-2) steps. We can then add these two numbers to get the total number of ways to reach the top from n steps.
- Take one step, then find the number of ways to reach the top from the remaining (4-1) steps, which is 3.
- Take two steps, then find the number of ways to reach the top from the remaining (4-2) steps, which is 2.
- The total number of ways to reach the top is 3+2 = 5.
int countWays(int n) {
if (n == 1 || n == 0) { // base case
return 1;
} else if (n == 2) { // base case
return 2;
} else {
return countWays(n-1) + countWays(n-2);
}
}
How Recursive Algorithms Works
When a function is called recursively, each instance of the function creates a new instance of the function on the call stack. The call stack keeps track of the function calls and their parameters and return values. When the base case is reached, the function calls are returned in reverse order until the original call is reached, and the final solution is returned.
Steps of Recursive Algorithm
- Identify the base case: The base case is the simplest version of the problem that can be solved directly without recursion. It is the terminating condition of the Recursive Algorithm.
- Identify the recursive case: The recursive case is the problem broken down into smaller subproblems of the same type. It is the part of the Recursive Algorithm that calls itself with a smaller subproblem.
- Solve the base case: Solve the simplest version of the problem directly without recursion.
- Solve the recursive case: Solve each subproblem recursively until the base case is reached.
- Combine the solutions: Combine the solutions of each subproblem to solve the original problem.
What is Base Condition of Recursion
In Recursion, the base condition is the condition that terminates the recursion. The base condition is the simplest version of the problem that can be solved directly without recursion. It is the terminating condition of the Recursive Algorithm.
It is important to ensure that the Recursive Algorithm has a base condition that is reachable and that the recursion will eventually terminate. Without a base case, the function will continue to call itself indefinitely(infinite recursion), causing the call stack to overflow and the program to crash.
For example, consider the following Recursive Algorithm for computing the factorial of a positive integer n:
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}
In this Recursive Algorithm, the base condition is when n == 0.
Nth Fibonacci Number using Recursive Algorithm
The Fibonacci series is a series of numbers in which each number is the sum of the two preceding numbers, starting with 0 and 1. The first few terms of the Fibonacci series are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Let's understand the recursive relation for the Fibonacci series. The nth number in the Fibonacci series can be calculated using the following formula:
F(n) = F(n-1) + F(n-2) When n <= 1, return n (Base Condition)where F(n) represents the nth number in the Fibonacci series, F(n-1) represents the (n-1)th number in the Fibonacci series, and F(n-2) represents the (n-2)th number in the Fibonacci series.
Using this recursive relation, we can write the following sample program for computing the nth number in the Fibonacci series using Recursive Algorithm:
#include <stdio.h>
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
int main() {
int n;
printf("Enter the value of n: ");
scanf("%d", &n);
printf("\nThe %dth number in the Fibonacci series is %d\n", n, fibonacci(n));
return 0;
}
Output
Enter the value of n: 7 The 7th number in the Fibonacci series is 13
Find Max Element of an Array using Recursive Algorithm
Let's understand the recursive relation for finding the maximum element of an array. The maximum element of an array can be found using the following formula:
max(A[0], A[1], ..., A[n-1]) = max(max(A[0], A[1], ..., A[n-2]), A[n-1])where A[0], A[1], ..., A[n-1] represent the elements of the array, and max(A[0], A[1], ..., A[n-1]) represents the maximum element of the array.
The base condition is when n == 1.
Using this recursive relation, we can write the following sample program for finding the maximum element of an array using Recursive Algorithm:
#include <stdio.h>
int find_max(int arr[], int n) {
if (n == 1) {
return arr[0];
} else {
int max = find_max(arr, n-1);
if (max > arr[n-1]) {
return max;
} else {
return arr[n-1];
}
}
}
int main() {
int arr[] = {10, 5, 20, 8, 15};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The maximum element in the array is %d\n",
find_max(arr, n));
return 0;
}
Output
The maximum element in the array is 20
Advantages and Disadvantages of Recursion
Advantages of Recursion
- Recursive Algorithms can be used to solve problems that have a natural recursive structure, such as trees, graphs, and other complex data structures.
- Recursive Algorithms can be more concise and elegant than their iterative counterparts, making them easier to read and understand.
- Recursive Algorithms can help break down complex problems into smaller subproblems, making it easier to solve the problem as a whole.
Disadvantages of Recursion
- Recursive Algorithms can be less efficient than their iterative counterparts, especially for large input sizes, due to the overhead of function calls and call stack management.
- Recursive Algorithms can be difficult to debug, since each recursive call creates a new instance of the function on the call stack, making it hard to trace the flow of execution.
- Recursive Algorithms can lead to stack overflow errors if the depth of recursion becomes too large, which can happen with certain input sizes or edge cases.
Difference between Recursive Algorithm and Iterative Algorithm
- Structure: Recursive Algorithm uses function calls to itself, whereas Iterative Algorithm uses loops.
- Time and Space Complexity: Recursive Algorithm has a higher time and space complexity due to the overhead of function calls and the stack space used by the algorithm. Iterative Algorithm has a lower time and space complexity since it does not use function calls.
- Ease of Understanding: Recursive Algorithm is easier to understand for problems that can be divided into smaller subproblems, whereas Iterative Algorithm is easier to understand for problems that require repetitive calculations.
- Tail Recursion Optimization: Recursive Algorithm can be optimized using Tail Recursion Optimization to reduce the overhead of function calls and the stack space used by the algorithm.
Common Examples of Recursive Algorithm
- Factorial Calculation: The factorial of a non-negative integer (denoted as n!) is calculated using a recursive algorithm n! = n x (n - 1)!.
- Binary Search: The binary search algorithm divides a sorted array in half at each step, recursively narrowing down the search space until the target element is found or the search space is empty.
- Merge Sort: Merge Sort is a divide-and-conquer sorting algorithm that recursively divides an array into two halves, sorts each half, and then merges them together.
- Quick Sort: Quick Sort is another divide-and-conquer sorting algorithm that recursively partitions an array based on a chosen pivot element and then sorts the resulting subarrays.
- Tower of Hanoi: The Tower of Hanoi problem involves moving a stack of disks from one peg to another, respecting the rules of the puzzle. It is often solved using recursion.