Recursion is a method of describing algorithms that allows a procedure
(or a function) to call itself. The `fct()`

function below is called itself:

```
void fct() {
...
fct();
}
```

The recursive form generally allows functions to be shorter and easier to understand. However, it may be less natural to design. When the problem addressed can be broken down into a succession of identical subproblems, recursion is generally a great option.

Let's consider the example of the `factorial()`

function which calculates the factorial
of an integer. We recall here the calculation of the factorial of \( n \):

$$ !n = 1 \times 2 \times 3 \times ... \times (n-1) \times n $$

The iterative way is the classic implementation (without recursion). Here is the code
of the`factorial()`

function ** without recursion **:

```
int factorial (int N) {
int i,fact=1;
for (i=2;i<=N;i++) fact*=i; // Iterate throught all the factors and multiply by i
return fact;
}
```

For the recursive form, we will rely on another writing of the factorial:

$$ !n = n \times !(n-1) $$

This equation allows the introduction of recursion because it involves the factorial (hence the recursion). Here is the implementation of the recursive function in C:

```
int factorial (int N) {
if (N<=1) return 1; // If N <= 1, returns 1 because !0=1 and !1=1
return N*factorial(N-1); // return N*!(N-1)
}
```

The recursive way is generally easier to understand and more elegant, it can be seductive in its intellectual conception. But the recursive calls save the context (the values of the variables) before each call and its return at the end of the call, which can slightly decrease the effectiveness of the program.

Write a recursive function `power()`

which calculates the power of two numbers: \(a ^ n \).
The prototype of the function is provided below:

`double power (double a, unsigned int n);`

The power calculation can be written in two ways:

$$ a^n = a \times a \times a ... a \times a $$

$$ a^n = a \times a^{n-1} $$

The second equation allows to introduce recursion. Here is an example of execution of the final program:

2^8 = 256.00 3^4 = 81.00 1.5^2 = 2.25

Write a recursive function `palindrome()`

which

- returns true if the word in argument is a palindrome
- and false otherwise. We will assume here that the character string does not contain spaces. The prototype is given below:

`int palindrome (const char *str, int length)`

`str`

is a pointer to the string.`length`

is the length of the string.

Enter a word: radar radar is a palindrome.

Enter a word: abracadabrantesque abracadabrantesque is not a palindrome.

** What is a recursive function? **

Check
Well done!
Try again...

** In general, is a recursive function faster than its iterative version? **

Check
Well done!
Try again...

** Each time the recursive function is called again, what happens to the local variables? **

Check
Well done!
Try again...

Last update : 11/23/2021