A Recursive function can be defined as a routine that calls itself directly or indirectly.
In other words, a recursive function is a function that solves a problem by solving smaller instances of the same problem. This technique is commonly used in programming to solve problems that can be broken down into simpler, similar subproblems.
Need of Recursive Function:
A recursive function is a function that solves a problem by solving smaller instances of the same problem. This technique is often used in programming to solve problems that can be broken down into simpler, similar subproblems.
1. Solving complex tasks:
Recursive functions break complex problems into smaller instances of the same problem, resulting in compact and readable code.
2. Divide and Conquer:
Recursive functions are suitable for divide-and-conquer algorithms such as merge sort and quicksort, breaking problems into smaller subproblems, solving them recursively, and merging the solutions with the original problem.
3. Backtracking:
Recursive backtracking is ideal for exploring and solving problems like N-Queens and Sudoku.
4. Dynamic programming:
Recursive functions efficiently solve dynamic programming problems by solving subproblems and combining their solutions into a complete solution.
5. Tree and graph structures:
Recursive functions are great for working with tree and graph structures, simplifying traversal and pattern recognition tasks.
How to write a Recursive Function:
Components of a recursive function:
Base case: Every recursive function must have a base case. The base case is the simplest scenario that does not require further recursion. This is a termination condition that prevents the function from calling itself indefinitely. Without a proper base case, a recursive function can lead to infinite recursion.
Recursive case: In the recursive case, the function calls itself with the modified arguments. This is the essence of recursion – solving a larger problem by breaking it down into smaller instances of the same problem. The recursive case should move closer to the base case with each iteration.
Let’s consider the example of factorial of number:
In this example, the base case is when n is 0, and the function returns 1. The recursive case multiplies n with the result of the function called with parameter n – 1. The process continues until the base case is reached.
It’s essential to ensure that the recursive function has a correct base case and that the recursive calls lead to the base case, otherwise, the procedure might run indefinitely, leading to a stack overflow (exceeding the available memory allocated for function calls).
Below is the implementation of factorial of a number:
C++
#include <iostream>
using namespace std;
int factorial(int n)
{
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
int main()
{
int n = 4;
cout << "Factorial of " << n
<< " is:" << factorial(n);
return 0;
}
|
Java
import java.util.Scanner;
public class Factorial {
static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
int n = 4;
int result = factorial(n);
System.out.println("Factorial of " + n + " is: " + result);
}
}
|
Python3
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
if __name__ == "__main__":
n = 4
print("Factorial of", n, "is:", factorial(n))
|
Output
Factorial of 4 is:24
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!