Recursive Patches
In computer science, recursion is the application of a function within its own definition. This method allows to solve complex problems.
In order no to "call itself" infinitely, a recursive function must include a termination condition . A termination condition is a necessary condition so that the function doesn't call itself.
Examples
The "factorial" function calculates the product of all positive integers that are inferior or equal to a given n number. It is written "n!". It is a widespread example of recursive function. .
n! is defined as follows : | It can also be defined recursively : |
|---|---|
For instance: fact(3) = 1 x 2 x 3 fact(n) = 1 x 2 x 3 x ... x (n-1) x n | fact(n) = n x fact (n - 1) For instance : fact(3) = 3 x (fact(3-1)) fact(3) = 3 x (2 x fact(2-1)) fact(3) = 3 x (2 x 1) And fact(1) = 1 |
The termination condition of the factorial function is fact(1) = 1.
It allows to calculate all the combinatorial possibilities of n elements, such as, for instance, the calculation of all possible melodic combinations of a group of notes.
The Fibonacci suite calculates the sum of a number of integers inferior or equal to n. It is another type of recursive function, which is written "f!".
"f!" is defined as follows : | It can also be defined recursively : |
|---|---|
fibo(n) = 1 + 2 + 3 + ... +(n-1) + n For instance: fact(6) = 1 + 2 + 3 + 4 + 5 + 6 | fibo(n) = n + fibo (n-1) For instance : fibo(6) = 6 + (fibo (5)) |
