Lesson 13.2. Depth of recursive functions

Depth

The depth of a recursive function is the number of times the function calls itself before reaching a stopping condition. In general, the depth of a recursive function increases as an input parameter to the function becomes larger.

The depth corresponds to the number of calls of the function. A traditional (non-recursive) function will have a depth of 1. A function with a depth of 5 means that it has called itself 4 times and has been called from the outside once (which we will call the main call). The depth is generally not an intrinsic property of the function but depends on the parameters that are passed to it.

Depth limit

A depth limit is a maximum allowed depth for a recursive function. This limit is put in place to prevent the function from entering an infinite recursion, where the function continues to call itself indefinitely.

In order to avoid infinite depths, a recursive function must necessarily include a stop test that ends the recursion. When the stop test is true, we execute the terminal recursion which is the action performed at the last call of the function. Without this stop condition, the calls will continue until the limit of the number of calls is reached or until the memory. Here is the recommended structure for a recursive function:

... Fct (...) {
  if (Test) {
    ...         // Terminal recursion (no recursive call)
  }
  else {
    ...
    Fct (...);  // Recursive call of the function
    ...
  }
}

Example

Let's take the example of the function factorial() which computes the factorial of an integer. The example below counts and displays the calls to the factorial() function.

Exercises

Exercise 1

We provide the recursive function power() that computes the power of two numbers (a^n)) based on the following relationship:

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

double power (double a, int n) {
  if (n==0) return 1;
  return a*power(a,n-1);
}

Measure the depth when calculating \( 2^{16} \).

2^16 = 65536.00

Exercise 2

We provide the recursive function power() that computes the power of two numbers (\(a^n\)) based on the following relationship:

$$ a^n = a^{ \dfrac{n}{2} } \times a^{ \dfrac{n}{2} } $$

double power (double a, int n) {

  double R;
  if (n==0) return 1.0;
  R=power (a,n/2);
  if (n%2==0) return R*R;
  return a*R*R;
}

Measure the depth when calculating \( 2^{16} \).

2^16 = 65536.00

Exercise 3

The Fibonacci sequence is defined as follows for \(n>1\) :

Initial values:

$$ f_0 = 0 $$ $$ f_1 = 1 $$

Definition:

$$ f_n = f_{n-1} + f_{n-2} $$

Write a function that calculates the Fibonacci number of order n. We assume that n is always greater than one in the main call. Measure the depth for n=20. What do you conclude from this?

Fibonacci(20) = 6765

Quiz

What is the depth of a recursive function?

Check Bravo! The depth is the number of calls of a recursive function including the main call. Try again...

Must a recursive function have a test?

Check Bravo! Without testing the function would enter an infinite recursion. Try again...

Terminal recursion ...

Check Bravo! The terminal recursion allows to stop the recursion. Try again...

See also


Last update : 12/06/2022