AS: Numerics - Recursion

2,560 Views | 5 Replies
New Topic Respond to this Topic

AS: Numerics - Recursion 2006-01-15 19:02:21

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.


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:


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

AS: Main

Response to AS: Numerics - Recursion 2006-01-15 19:19:06

heh, simple grade 10 maths

Response to AS: Numerics - Recursion 2006-01-15 19:32:37

i love recursion but i always seem to have problems with it, like the bullet reflection thing ive been working on(here ) or that old minesweeper game i was working on(here)

i seem to have no luck with recursion.

This blog I made | This game sucks | I, twit

Just trying to get enough Twitter followers to quit Facebook forever

Response to AS: Numerics - Recursion 2006-01-15 19:40:54

nice, now bother covering stuff recursion is really useful for like merge and quick sort, binary trees and so on.

Keep up the great work on these :)

Response to AS: Numerics - Recursion 2006-01-15 19:47:20

At 1/15/06 07:02 PM, Sekky wrote: Numerics - Recursion

this is actually really good. its very hard to explain concepts like this, because, save for specific examples like factorials, you cant show someone how to come up with concepts of their own. there is more you could have covered, but this is an adequate "intro to recursion".

BBS Signature

Response to AS: Numerics - Recursion 2006-01-16 11:43:06

Hmm, some simply concepts, this seems to be stepping away fromAS and into applied math. Though the good old no of characters in selection! / no of repeats! is good for possible combos.

Maybe another demo:

10 balls in a bag 5 blue 2 red and 3 green , pick 1 one replace it , repeat 5 times.

Probablity of getting 3 blue and 2 red =

3! *2!

=120 / 12
= 10