# 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 numberint 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 functionsvoid foo1(void);void foo2(void);// defining recursive functionsvoid 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; }