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 caseif (x == 0){return x;}// recursive caseelse{return square(x-1) + (2*x) - 1;}}int main() {// implementation of square functionint 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 nn++; // increments n by 1foo2(); // calls foo2()}elsereturn;}void foo2(){if (n <= 20){cout<<n<<" "; // prints nn++; // increments n by 1foo1(); // calls foo1()}elsereturn;}// Driver Programint main(void){foo1();return 0;}