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.

Try online

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

Do the exercise

Solution

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

Do the exercise

Solution

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

Do the exercise

Solution

Quiz

What is the depth of a recursive function?

The number of lines of code in the function

the number of calls of the function only from another function

the number of recursive calls including the main call

the number of recursive calls without the main call

Check

Must a recursive function have a test?

never

always

it is optional

it is mandatory for the terminal recursion

Check

Terminal recursion ...

is the first call of a recursive function

is the last call of a recursive function

calls the recursive function from itself

no longer calls the recursive function

Check

Lesson 13.1 Summary Lesson 13.3

Lesson 13.2. Depth of recursive functions

Depth

Depth limit

Example

Exercises

Exercise 1

Exercise 2

Exercise 3

Quiz

See also