BeginnersBook

  • Home
  • Java
    • Java OOPs
    • Java Collections
    • Java Examples
  • C
    • C Examples
  • C++
    • C++ Examples
  • DBMS
  • Computer Network
  • Python
    • Python Examples
  • More…
    • jQuery
    • Kotlin
    • WordPress
    • SEO
    • JSON
    • JSP
    • JSTL
    • Servlet
    • MongoDB
    • XML
    • Perl

C++ Recursion with example

Last Updated: September 11, 2017 by Chaitanya Singh | Filed Under: Learn C++

The process in which a function calls itself is known as recursion and the corresponding function is called the recursive function. The popular example to understand the recursion is factorial function.

Factorial function: f(n) = n*f(n-1), base condition: if n<=1 then f(n) = 1. Don’t worry we wil discuss what is base condition and why it is important.

In the following diagram. I have shown that how the factorial function is calling itself until the function reaches to the base condition.

C++ recursion

Lets solve the problem using C++ program.

C++ recursion example: Factorial

#include <iostream>
using namespace std;
//Factorial function
int f(int n){
   /* This is called the base condition, it is
    * very important to specify the base condition
    * in recursion, otherwise your program will throw
    * stack overflow error.
    */
   if (n <= 1)
        return 1;
   else 
       return n*f(n-1);
}
int main(){
   int num;
   cout<<"Enter a number: ";
   cin>>num;
   cout<<"Factorial of entered number: "<<f(num);
   return 0;
}

Output:

Enter a number: 5
Factorial of entered number: 120

Base condition

In the above program, you can see that I have provided a base condition in the recursive function. The condition is:

if (n <= 1)
        return 1;

The purpose of recursion is to divide the problem into smaller problems till the base condition is reached. For example in the above factorial program I am solving the factorial function f(n) by calling a smaller factorial function f(n-1), this happens repeatedly until the n value reaches base condition(f(1)=1). If you do not define the base condition in the recursive function then you will get stack overflow error.

Direct recursion vs indirect recursion

Direct recursion: When function calls itself, it is called direct recursion, the example we have seen above is a direct recursion example.

Indirect recursion: When function calls another function and that function calls the calling function, then this is called indirect recursion. For example: function A calls function B and Function B calls function A.

Indirect Recursion Example in C++

#include <iostream>
using namespace std;
int fa(int);
int fb(int);
int fa(int n){
   if(n<=1)
      return 1;
   else
      return n*fb(n-1);
}
int fb(int n){
   if(n<=1)
      return 1;
   else
      return n*fa(n-1);
}
int main(){
   int num=5;
   cout<<fa(num);
   return 0;
}

Output:

120
❮ PreviousNext ❯

Top Related Articles:

  1. Operators in C++
  2. goto statement in C++ with example
  3. Function Overriding in C++
  4. Function Overloading – Call of Overloaded Function is ambiguous
  5. Data Types in C++

About the Author

I have 15 years of experience in the IT industry, working with renowned multinational corporations. Additionally, I have dedicated over a decade to teaching, allowing me to refine my skills in delivering information in a simple and easily understandable manner.

– Chaitanya

Comments

  1. Raza says

    October 18, 2017 at 11:04 AM

    Nice Example!
    I have one question, when the base condition is reached, shouldn’t the function return ‘1’ to main call rather the result accumulated i.e ‘120’?

    Reply
    • Shadow3641 says

      April 17, 2018 at 11:14 PM

      No, because it queues up the multiplier from the first function call of the n*f(n-1). So when n is finally <= 1 it returns it to the function call before. So instead of n* f(n-1), it would be n * 1. From here it would have all the previous values of n stored and solve the equation.

      Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Copyright © 2012 – 2025 BeginnersBook . Privacy Policy . Sitemap