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.

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

The iterative way is the classic implementation (without recursion). Here is the code
of the`factorial()`

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

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.

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

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.

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

- 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.2. Depth of recursive functions
- Lesson 13.2. Mutual recursion
- Lesson 14.1. Additional exercises

Last update : 12/05/2022