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.

Press + to interact
void directRecursionFunction()
{
  // some code...
  directRecursionFunction();
  // some code...
}

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

Press + to interact
#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.

Press + to interact
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.

What is an example of indirect recursion?

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

Press + to interact
#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; 
}

Conclusion

In conclusion, we learned that direct recursion happens when a function invokes itself directly within its body, creating a loop of self-calls that can be resolved through a base case. This straightforward recursion method is useful for problems that can be broken down into similar subproblems. Alternatively, indirect recursion involves at least two functions working together. In this scenario, one function calls a second function, which then calls the original function back, creating a recursive loop between them. This type of recursion can be advantageous for more complex scenarios where a single function alone cannot effectively solve the problem.