Direct vs. Indirect Recursion

This lesson explains two different types of recursion: direct and indirect recursion.

We'll cover the following

Direct Recursion

If a function calls itself, it’s known as direct recursion. This results in a one-step recursive call: the function makes a recursive call inside its own function body.

void directRecursionFunction()
{
  // some code...
  directRecursionFunction();
  // some code...
}

Below is an example of a direct recursive function that computes the square of a number:

#include <iostream>
using namespace std;
// recursive function to calculate square of a number
int square(int x)
 {
  // base case
    if (x == 0)
    {
      return x; 
    }
  // recursive case
  else 
   {
      return square(x-1) + (2*x) - 1;
   }
}
int main() {
  // implementation of square function
  int input=30;
  cout << input<<"^2 = "<<square(input);
  return 0;
}

Indirect Recursion

If the function f1 calls another function f2 and f2 calls f1 then it is indirect recursion (or mutual recursion).

This is a two-step recursive call: the function calls another function to make a recursive call.

void indirectRecursionFunctionf1();
void indirectRecursionFunctionf2();
  
void indirectRecursionFunctionf1()
{
  // some code...
  indirectRecursionFunctionf2();
  // some code...
}
void indirectRecursionFunctionf2()
{
  // some code...
  indirectRecursionFunctionf1();
  // some code...
}

Note: For indirect recursion, both the functions need to be declared before they are defined.

Below is an implementation of indirect recursion that prints the first 20 integers:

#include <iostream>
using namespace std;
int n=0;
// declaring functions
void foo1(void);
void foo2(void);
// defining recursive functions
void foo1() 
{ 
  if (n <= 20) 
  { 
    cout<<n<<" ";  // prints n
    n++;           // increments n by 1
    foo2();       // calls foo2() 
  } 
  else
    return; 
} 
void foo2() 
{ 
  if (n <= 20) 
  { 
    cout<<n<<" ";  // prints n
    n++;           // increments n by 1
    foo1();       // calls foo1()
  } 
  else
    return; 
} 
// Driver Program 
int main(void) 
{ 
  foo1(); 
  return 0; 
}