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.

Try online

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

Do the exercise

Solution

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
radar is a palindrome.

Enter a word: abracadabrantesque
abracadabrantesque is not a palindrome.

Do the exercise

Solution

Quiz

What is a recursive function?

A function with a loop inside

A function that calls another function

A function that call itself

A function that never ends

Check

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

Much slower

Slightly slower

Slightly faster

Much faster

Check

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

Local variables are saved on the stack.

This is hat we call context saving.

Local variables are lost (memory if freed).

Local variables are kept only if they are static.

Check

Lesson 12.4 Summary Lesson 13.2

Lesson 13.1. Recursive functions in C

Introduction

Example

Iterative function

Recursive function

Exercises

Exercise 1

Exercise 2

Quiz

See also