Recursive Functions
Last Updated :
23 Nov, 2023
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))
|
C#
using System;
class Program
{
static int Factorial(int n)
{
if (n == 0)
{
return 1;
}
return n * Factorial(n - 1);
}
static void Main()
{
int n = 4;
Console.WriteLine("Factorial of " + n + " is: " + Factorial(n));
}
}
|
Javascript
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
}
function main() {
let n = 4;
let result = factorial(n);
console.log("Factorial of " + n + " is: " + result);
}
main();
|
Output
Factorial of 4 is:24
Time Complexity: O(n)
Auxiliary Space: O(n)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...