AS: Numerics - Recursion

• 1,792 Views
• 5 Replies
Sekky
Sekky
• Member since: Mar. 17, 2003
• Offline.
Forum Stats
Member
Level 24
Blank Slate
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.

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

AS: Main

shazwoogle
shazwoogle
• Member since: Sep. 27, 2004
• Offline.
Forum Stats
Member
Level 11
Blank Slate
Response to AS: Numerics - Recursion 2006-01-15 19:19:06

heh, simple grade 10 maths

GeoKureli
GeoKureli
• Member since: Apr. 1, 2003
• Offline.
Forum Stats
Supporter
Level 19
Game Developer
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.

Inglor
Inglor
• Member since: Jan. 26, 2003
• Offline.
Forum Stats
Member
Level 17
Blank Slate
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 :)

authorblues
authorblues
• Member since: Jun. 21, 2005
• Offline.
Forum Stats
Member
Level 12
Blank Slate
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".

T-H
T-H
• Member since: Jan. 7, 2004
• Offline.
Forum Stats
Member
Level 40
Blank Slate
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 =

5!
-------
3! *2!

=120 / 12
= 10

BBBRR
BBRBR
BRBBR
RBBBR
RBBRB
RBRBB
RRBBB
BRRBB
BBRRB
BRBRB