## C++ Recursion

Recursion is a process in which function calls itself repeatedly until a certain condition is met and the corresponding function is called the recursive function. A function said to be recursive if a function calls itself.

## Factorial Function

We will discuss factorial function using recursion.

Syntax Of Factorial Functions

```fact(int n)
{
if(n==1) return 1;
else
return n*fact(n-1);   // recursive call, fact() calling itself
}```

So the above function fact() invokes itself to find the factorial of n - 1.

Say for the first time n=4.
1. fact(4) = { (4==1) is false thus return 4*fact(3) }
2. fact(3) = { (3==1) is false thus return 3*fact(2) }
3. fact(2) = { (2==1) is false thus return 2*fact(1) }
4. fact(1) = { (1==1) is true thus return 1 }

The result of fact (1) returning to step 3, fact (2) 2 * 1 then returning to fact (3), which is 3 * 2 * 1 and finally fact (4) returning 4 * 3 * 2 * 1 which Is equal to 24.

Example Of Factorial Functions

```#include
using namespace std;
int f(int n)
{
if (n <= 1)
return 1;
else
return n*f(n-1);
}

int main()
{
int num;
cout<<"Enter a number: ";
cin>>num;
cout<<"Factorial of entered number: "<< f(num);
return 0;
}```

Output :
```Enter a number: 5
Factorial of entered number: 120```

In the example above, the f() function is used to calculate the Factorial of entered number.

## Return Function

Return function is used to return the control to calling function. A function terminates either by the return statement or when it reaches to the end of the statments.

Syntax

The general form of return statement is as follows:

`Factorialreturn(value);`

A void function can do return

```void func()
{
cout << "A void function can do return";

// We can write return in void
return;
}

int main()
{
func();
return 0;
}```

Output:

`A void function can do return`

A void fun() can return another void function

```void func()
{
cout << "The void function has returned "
" a void() !!! \n";
}

// Driver void() returning void work()
void xyz()
{
// Returning void function
return func();
}

int main()
{
// Calling void function
xyz();
return 0;
}
```

Output:

```The void function has returned a void() !!!
```

A void() can return a void value

```#include<iostream.h>
using namespace std;
void xyz()
{
cout << "A void() can return a void value";

// Returning a void value
return (void)"Doesn't Print";
}
int main()
{
xyz();
return 0;
}```

Output:

`A void() can return a void value`

## Exercise:-

1. In which circumstances recursion function is called?

A. To call the same function again inside the function itself
B. For calling maths function
C. To calling input and output stream
D. All of them

2. Recursive call is also known as

A. Complex calls
B. Operator call
C. Recursion step
D. None of them

## Program :-

Program for Fibonacci numbers

```#include<bits/stdc++.h>
using namespace std;

int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}

int main ()
{
int n = 9;
cout << fib(n);
getchar();
return 0;
} ```

Output :

```34
```

Visit :

Discussion