# lesson 13.1. Recursive functions in C

## Introduction

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.

## Example

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$$

### Iterative function

The iterative way is the classic implementation (without recursion). Here is the code of thefactorial() 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;
}

### Recursive function

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.

## Exercises

### Exercise 1

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


### Exercise 2

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

Enter a word: abracadabrantesque


## Quiz

What is a recursive function?

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

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