Recursive Function In C++

Posted on December 14, 2023 by Vishesh Namdev

Python C C++ Javascript Java

Recursion in C++ programming refers to a programming technique where a function calls itself to solve a problem. It is a powerful and elegant approach to solving complex problems that can be broken down into smaller, similar subproblems. Recursion is based on the principle of "divide and conquer," where a larger problem is divided into smaller, more manageable subproblems, and the results are combined to solve the original problem..

How does a Recursion Function work in C++:

1. Function Call: The recursive function is called with a specific input.

2. Base Case Check: Base Case Check: Inside the function, there's a check for a base case. The base case is a condition that, when met, stops the recursion. If the base case is satisfied, the function returns a result immediately.

3. Recursive Case: If the base case is not met, the function calls itself with a modified or simpler version of the original problem. The idea is to break down the problem into smaller, more manageable subproblems.

4. Stack Frame: Each function call creates a new stack frame, which contains the function's local variables, parameters, and return address. These stack frames are stored on the call stack.

5. Return Values: When the base case is reached, the function returns a value. If it's not the base case, the function returns the result of the recursive call.

6. Backtracking : As the recursive calls complete, the stack frames are popped off the call stack in a last-in, first-out (LIFO) fashion. This is the process of backtracking, which allows the program to continue and combine results from multiple recursive calls.

Base Condition in Recursion Functions:

#include <iostream> Copy Code
// Function overloading with different parameter types
int add ( int a, int b) {
return a + b;
}
double add ( double a, double b) {
return a + b;
}

// Function overloading with a different number of parameters
int add ( int a, int b, int c) {
return a + b + c;
}

// Main function
int main () {
// Calling the overloaded functions
int sum1 = add (3, 4);
double sum2 = add (2.5, 3.5);
int sum3 = add (1, 2, 3);

// Displaying the results
std::cout << "Sum 1: " << sum1 << " " ;
std::cout << "Sum 2: " << sum2 << " " ;
std::cout << "Sum 3: " << sum3 << " " ;
return 0;
}

In this example, the base condition is if (n <= 0), which stops the recursion when n becomes less than or equal to 0. The function prints "Blastoff!" and returns without making another recursive call.

Recursion Case:

The recursive condition defines how the function calls itself with a modified set of parameters, moving towards the base condition. In a well-designed recursive function, each recursive call should bring the problem closer to the base condition, ensuring progress towards termination.

Here's an example of Recursion Function :

#include <iostream> Copy Code
// Function to calculate factorial recursively
int factorial ( int n) {
// Base condition: Stop when n is 0 or 1
if (n == 0 || n == 1) {
return 1;
}

// Recursive condition: Call the function with a smaller value
return n * factorial (n - 1);
}

// Main function
int main () {
// Example of using a recursive function to calculate factorial
int result = factorial (5);
std::cout << "Factorial of 5 is: " << result << " " ;
return 0;
}

In this example, the base condition is if (n == 0 || n == 1), which stops the recursion when n is 0 or 1. The recursive condition is return n * factorial(n - 1), where the function calls itself with a smaller value of n.

1. Base Condition: Provides the termination criterion for the recursion, stopping the function from making further recursive calls.
2. Recursive Condition: Describes how the function calls itself with a modified set of parameters, bringing the problem closer to the base condition.