# Recursion

Recursive programming is a procedure in which a method calls itself, so that a problem is solved more and more with each method call. This continues until the problem is reduced to a very simple case.

Some tasks in computer science can be solved well by reducing a large problem step by step to smaller and smaller problems of the same kind until simple (trivial) solutions arise . From this finally the solution of the original large problem is put together.

## Syntax

``````return_type function_name(type parameter) {
// code to be executed
return function_name(type parameter)
}``````

## Example: factorial

This is a simple C++ program that implements a recursive function `factorial` to calculate the factorial of a given positive integer `number`.

The function `factorial` takes an integer `number` as an argument and returns the factorial of that number. If the `number` is less than 2, the function returns 1, which is the base case of the recursion. Otherwise, the function returns the `number` multiplied by the result of the `factorial` function called with `number - 1`. This causes the function to be called repeatedly with smaller values of `number` until the base case is reached.

In the `main` function, the factorial of 8 is calculated by calling the `factorial` function with the argument `8` and the result is printed to the console using the `cout` statement.

``````#include &lt;iostream&gt;
using namespace std;

int factorial(int number) {
if (number < 2) {
return 1;
} else {
return number * factorial(number - 1);
}
}

int main() {
cout << "factorial of 8 is " << factorial(8);

return 0;
}``````
##### Output
``factorial of 8 is 40320``

## Example: fibonacci

This is a simple C++ program that implements a recursive function `fibonacciAlgorithm` to calculate the n-th number in the Fibonacci sequence.

The function `fibonacciAlgorithm` takes an integer `number` as an argument and returns the n-th number in the Fibonacci sequence. If the `number` is 0 or 1, the function returns `number`, which is the base case of the recursion. Otherwise, the function returns the sum of the results of two recursive calls to `fibonacciAlgorithm` with the arguments `number - 1` and `number - 2`. This causes the function to be called repeatedly with smaller values of `number` until the base case is reached.

In the `main` function, the 10th number in the Fibonacci sequence is calculated by calling the `fibonacciAlgorithm` function with the argument `10` and the result is printed to the console using the `cout` statement.

``````##include &lt;iostream&gt;
using namespace std;

int fibonacciAlgorithm(int number) {
if (number == 0 || number == 1) {
return number;
} else {
return fibonacciAlgorithm(number - 1) + fibonacciAlgorithm(number - 2);
}
}

int main() {
cout << "fibonacci number of the number 10 is " << fibonacciAlgorithm(10);

return 0;
}``````
##### Output
``fibonacci number of the number 10 is 55``