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

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 ❯

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 *

C++ Tutorial

  • C++ Tutorial
  • First C++ Program
  • C++ Variables
  • C++ Data types
  • C++ Operators

Flow Control

  • C++ If-else
  • C++ Switch Case
  • C++ for loop
  • C++ while loop
  • C++ do-while loop
  • C++ Continue
  • C++ break
  • C++ goto

Functions

  • C++ Functions
  • Default Argument in Function
  • C++ Recursion

Arrays

  • C++ Arrays
  • Multidimensional Arrays
  • C++ Array to Function
  • C++ Strings

Pointers

  • C++ Pointers
  • "this" Pointer

OOPs Concepts

  • C++ OOPs
  • C++ Constructor
  • C++ Destructor
  • C++ Structure
  • Struct and Function
  • C++ Enum
  • C++ Inheritance
  • C++ Polymorphism
  • C++ Function Overloading
  • C++ Function Overriding
  • Function Overloading vs Overriding
  • C++ Virtual Function
  • Encapsulation
  • Abstraction
  • C++ Interfaces
  • Friend Class and Function

Copyright © 2012 – 2022 BeginnersBook . Privacy Policy . Sitemap