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

int palindrome (const char *str, int length)
Enter a word: radar
radar is a palindrome.
Enter a word: abracadabrantesque
abracadabrantesque is not a palindrome.

Quiz

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

See also


Last update : 11/23/2021