Recursion in C++

Recursion in C++ Programming

In this page, we have explained all about recursion in C++ program which includes the different types of recursion in C++.
Recursion in C++

What is Recursion in C++?

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. A recursive function is a function that calls itself with a smaller input until it reaches a base case, at which point it returns a result.

Example of a recursive function in C++ that calculates the factorial of a given number:

Run
#include <iostream>
using namespace std;

int factorial(int n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

int main()
{
  int num;
  cout << "Enter a number: "; cin >> num;

  int result = factorial(num);
  cout << "The factorial of " << num << " is " << result << endl;

  return 0;
}

Output

Enter a number: 7
The factorial of 7 is 5040

Types of Recursion

There are two main types of recursion in C++:

  1. Tail recursion
  2. Non-tail recursion

Tail Recursion

  • This is a type of recursion where the recursive call is the last thing the function does before returning a value.
  • Tail-recursive functions are generally preferred over non-tail-recursive functions because they can be optimized by the compiler.
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

Non Tail Recursion

  • This is a type of recursion where the recursive call is not the last thing the function does before returning a value.
  • Non-tail-recursive functions are generally less efficient than tail-recursive functions because they cannot be optimized by the compiler.
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int result = factorial(n - 1);
  return n * result;
}

Program to calculate the nth number in the Fibonacci sequence using Recursion

Run
#include <iostream>
using namespace std;

int fibonacci(int n)
{
  if (n <= 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fibonacci (n - 1) + fibonacci (n - 2);
}

int main()
{
  int num;
  cout << "Enter a number: ";
  cin >> num;

  int result = fibonacci(num);
  cout << "The " << num << "th number in the Fibonacci sequence is " << result << endl;

  return 0;
}

Output

Enter a number: 13
The 13th number in the Fibonacci sequence is 233

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription