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.

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

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.

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

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

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

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

- Learn C programming
- Lesson 1.1. History of C programming language
- Lesson 1.2. First program
- Lesson 1.3. Compilation
- Lesson 1.4. Preprocessor directives
- Lesson 1.5. Which compiler to choose?
- Lesson 1.6. Flowchart
- Lesson 2.1. Types and variables
- Lesson 2.2. Integers
- Lesson 2.3. Floating point numbers
- Lesson 2.4. Characters
- Lesson 2.5. Variables initialization
- Lesson 2.6. Ariane flight 501
- Lesson 3.1. Arithmetic operators
- Lesson 3.2. modulo
- Lesson 3.3. Operators and types
- Lesson 3.4. Type casting
- Lesson 3.5. Bitwise operators
- Lesson 3.6. Bitwise operators details
- Lesson 3.7. Shifting operators
- Lesson 3.8. Assignment operators
- Lesson 3.9. Increment and decrement operators
- Lesson 3.10. Comparison operators
- Lesson 3.11. Logical operators
- Lesson 3.12. Operator precedence
- Lesson 4.1. printf
- Lesson 4.2. scanf
- Lesson 4.3. putchar
- Lesson 5.1. Conditional branching (if...else)
- Lesson 5.2. Nested if and indentation
- Lesson 5.3. Checking intervals
- Lesson 5.4. Ternary Operator ?:
- Lesson 5.5. switch..case statement
- Lesson 5.6. Break keyword in switch..case
- Lesson 6.1. do..while loop in C
- Lesson 6.2. While loop in C
- Lesson 6.3. For loop in C
- Lesson 6.4. How to choose the right loop in C ?
- Lesson 6.5. Exercices on loops in C
- Lesson 7.1. Bit masking
- Lesson 7.2. Bit masking, how to clear a bit in C?
- Lesson 7.3. Bit masking, how to set a bit in C?
- Lesson 7.4. Bit masking, how to toggle a bit in C?
- Lesson 7.5. Bit masking, how to check a single bit in C?
- Lesson 7.6. Overview of bit masking
- Lesson 8.1. Basic syntax of C functions
- Lesson 8.2. Calling C functions
- Lesson 8.3. Void keyword
- Lesson 8.4. Return keyword
- Lesson 8.5. Variable scope
- Lesson 8.6. Global variables
- Lesson 8.7. Static variables
- Lesson 8.8. Random numbers in C
- Lesson 8.9. Mathematical functions in C
- Lesson 9.1. Syntax of C arrays
- Lesson 9.2. Array initialization
- Lesson 9.3. Multidimensional arrays
- Lesson 9.4. How C arrays are stored in memory?
- Lesson 9.5. Arrays and functions
- Lesson 9.6. Exercises on C arrays
- Lesson 10.1. Strings in C
- Lesson 10.2. Null terminated string
- Lesson 10.3. The string.h library
- Lesson 10.4. String and functions
- Lesson 11.1. Introduction to pointers in C
- Lesson 11.2. Syntax of C pointers
- Lesson 11.3. Dynamic memory allocation
- Lesson 11.4. Incrementing pointers
- Lesson 11.5. Pointers as function argument in C
- Lesson 12.1. Introduction to structures in C
- Lesson 12.2. Properties of structures in C
- Lesson 12.3. Structures and pointers
- Lesson 12.4. Structures and functions
- Lesson 13.1. Recursive functions in C
- Lesson 13.2. Mutual recursion
- Lesson 14.1. Additional exercises

Last update : 12/06/2022