OpenMusic 6 – User ManualHierarchie de section : Advanced Visual Programming > Abstraction > Recursive PatchesRecursive Patches
In computer science, recursion is the application of a function within its own definition. This method allows to solve some 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 is written "n!". It is a widespread example of recursive function. It calculates the produce of all positive integers that are inferior or equal to n.
|
n! is defined as follows : |
It can also be defined recursively : |
|---|---|
|
fact(n) = 1 * 2 * 3 * ... * (n-1) * n For instance: fact(3) = 1 * 2 * 3 |
fact(n) = n* fact (n - 1) For instance : fact(3) = 3 * (fact(3-1)) fact(3) = 3 * (2 * fact(2-1)) fact(3) = 3 * (2 * 1) |
Hence, 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)) |
