Numerics - Recursion
What is Recursion?
A recursive sequence uses the previous term to calculate the next term in the sequence. Examples of this are Fibonacci's sequence, where the next term is the previous two added together.
Why do we need Recursion
Well, strictly we don't, you could work everything out by hand, but this makes things so much easier. I'll be demonstrating a few examples of recursion and their small applications here, and move onto more sophisticated applications in later tutorials.
The Fibonnacci Sequence
function Fibonacci(n) {
if (n < 2) { return n }
else return (Fibonacci(n-1) + Fibonacci(n-2));
}
By entering a number n into the function, it will return the nth term in the sequence by returning the previous two (ie Fib(n-1) and Fib(n-2)) added together, it is likely that these two will also return the previous two added together, and so on. You can also use this Function to calculate the golden ratio, defined by the quotient of two consequetive Fibonaccis.
Factorials
Yes, Fiboonacci is useless Math when it comes to programming, but now you've seen recursion, we can use it in a much better application, Factorials.
A Factorial of a number n is defined by the product of all positive integers less than or equal to n. Written as n!. For example 5! would be 5*4*3*2*1 = 120. You can probably see that recursion will come in handy here.
function Factorial(n) {
if (n < 2) { return n }
return n*Factorial(n-1);
}
This function will return the current number multiplied by the Factorial of the number below it, which will do the same in turn until it reaches 1. The factorial has a large use in statistics in determining probability. The combination formula:
n!/(k!(n-k)!
determines how many different ways k number of objects can be made from n number of objects. Putting this formula quickly into a function:
function Choose(N,K) {
return Factorial(N)/(Factorial(K)*Factorial(N-K))
}
We can quickly determine large odds very quickly. For example, choosing four aces from a pack of cards. The function will determine how many different combinations of four cards there are in a deck of 52 by calling the function Choose(52,4), or perhaps lottery odds, by calling the function Choose(49,6).
This can aid you greatly in statistical probability, which I will be covering sometime soon
