# Direct vs. Indirect Recursion

There are different ways to think about recursion. One way to see if a function calls itself directly or if it is called by some other function. In this tutorial, we will focus on this type of categorization. So let’s get started.

## Direct Recursion

When a function calls itself directly within its own body then it is called direct recursion.

Example:

```
int fun(int n)
{
if (n == 1)
return 1;
else
return 1 + fun(n-1);
}
```

## Indirect Recursion

In indirect recursion, a function calls another function which in turn call the original function. This creates a chain of function calls that eventually leads back to the original function.

**Note**: there can be multiple function calls in between. The essence of indirect recursion lies in the fact that the function does not call itself directly within its own body, but is indirectly called by some other function which it calls.

Example:

```
int fun1(int n)
{
if (n == 1)
return 1;
else
return 1 + fun2(n-1); // calling fun2
}
int fun2(int n)
{
if (n == 1)
return 1;
else
return 1 + fun1(n-1); // calling fun1
}
```

## Practical Applications

### Direct Recursion

Following are the applications of direct recursion which we already saw in our previous tutorials:

- Finding the factorial of a number.
- Finding the nth Fibonacci number.

And, there are many more applications of direct recursion.

### Indirect Recursion

**Program**: check if a number is even or odd.

```
#include <stdio.h>
int odd(int);
int even(int);
int even(int n)
{
// Base case: 0 is even.
if (n == 0)
return 1;
else
return odd(n-1); // calling odd
}
int odd(int n)
{
// Base case: 0 is not even
if (n == 0)
return 0;
else
return even(n-1); // calling even
}
int main()
{
int n;
printf("Enter a number: ");
scanf("%d", &n);
// check if the number is even.
if (even(n)) {
printf("Number is even.");
} else {
printf("Number is odd.");
}
return 0;
}
```

**Output:**

```
Enter a number: 68
Number is even.
```

**Explanation:**

The program is using indirect recursion to check if a number is even or odd. Within the `main()`

function, `even()`

function is called. If the number is even then eventually the base case of the `even()`

function will be true. If not, then the base case of the `odd()`

function will be true.

For example, consider that n is 2. The `even()`

function is called. The base case is not true as n is not equal to 0, therefore the `odd()`

function is called with value 1. In the `odd()`

function also the base case is not true, so the `even()`

function is called, and this time the base case condition is satisfied. This means the number is even, and that’s true 😎

Now, you can easily verify the program on your own by providing different values of n to the `even()`

function.

This is one application of indirect recursion, but there are many use cases where indirect recursion makes more sense and works correctly.

## Summary

- Direct recursion means a function calls itself within its own body.
- Indirect recursion refers to a function calling another function which in turn calls the original function.

## Test Your Knowledge

Question 1:

Which of the following is an example of indirect recursion?

void A() { A(); }

void A() { B(); } void B() { A(); }

void A() {}

void A() { return; }

explanation

Indirect recursion happens when a function calls another function which in turn calls the first function.

Question 2:

Which statement is true about indirect recursion?

Only one function is involved.

No function calls itself.

Two or more functions are involved.

The recursion terminates after one call.

explanation

Indirect recursion involves two or more functions calling each other in a cyclic manner.

Question 3:

Determine the output of the following program:

```
#include <stdio.h>
void A(int);
void B(int);
void B(int n) {
if (n > 0) {
printf("%d ", n);
A(n-1);
}
}
void A(int n) {
if (n > 1) {
printf("%d ", n);
B(n/2);
}
}
int main() {
A(4);
return 0;
}
```

explanation

In the given program, `A(4)`

is called and value 4 is printed. Within the body of `A(4)`

, `B(2)`

is called and the value 2 is displayed. `B(2)`

then calls `A(1)`

, but this time the condition `n > 1`

is not satisfied. There nothing will be evaluated and eventually we return back to main. The final output is clearly 4 2.

Your score is out of

## Leave a comment