recursive factorial recursive exponent

Practical Recursion

Factorial & Exponent

by Robert Deveau 2013


Return to Practical Recursion Home





Lottery Odds Calculator



Does the order matter?
Yes
No
Is repetition allowed?
Yes
No

The Simplest Recursion

Factorial and Exponent functions are examples of single tail recursion. Notice the pattern: the base case goes in an If statement, and the recursive call goes in the return statement.



Trace the Activation stack in your head with N=3. Recall that a stack is a Last In First Out (LIFO) structure much like the trays in a cafeteria. The new trays are placed on top and removed from the top. This is done to death at many iternet sites. So, I will cover it quickly. Suppose I put the number 3 in the text box (lets trace the stack) Our initial call will be call factorial (3),
which wants to return 3* factorial(2);, but it cant because there is another function call and must wait for that function call to return. So, it gets placed on the stack until the base case is read (number = 0). the stack will look like this:

We stack up the function calls from the bottom up, and pop them off from the top down. Well, we don't do it, that is just how the program stack works.

Now lets try that with the exponent function. Take some arbitrary integer and power e.g. 56.
Remember our objective is to solve our problem with the programming language of our choice and to think recursively as opposed to iteratively. So, do not use any For or While loops

"To iterate is human; to recurse divine." - Alexander Pope.
You will likely write your algorithm in psuedo-code on a piece of paper and have many comments in your code so you can understand what you did next year. However, the release versions of code seldom contain explanations.
It is up to the next programmer to figure out what was done.

"A cathedral isn't a cathedral until the last piece of scaffolding is removed."-Karl Friedrich Gauss (1777-1855)

Keep good records of what you did. Because, you will have to use that scaffolding for the next problem (cathedral) coming up!

base to the power of


Combinations and Permutations

Learn how to use the nCr and nPr keys on your calculator.

Those keys assume that repetition is not allowed! To use your calculater to compute the odds of winning various games of chance, you will need to use these formulas.

I'll save the Math lesson for you to look up. However I do encourage you to look up their derivation.

GameTypeFormulaRandom Generator
Pick 3 Box (0-9)combination/repetition(N+r-1)!/R!(N-1)!
Pick 3 straight (0-9)permutation/repetitionNRLike a combination Lock
Pick 4 Box (0-9)combination/repetition(N+r-1)!/R!(N-1)!
Pick 4 Straight (0-9)permutation/repetitionNR
Rack-em up (1-16)permutation/no-repetitionN!/(N-R)!This is your nPr key on your calculator
Powerball (0-59) + (0-35)combination/no-repetitionN!/R!(N-R)!This is your nCr key on your calculator.

Locks

Use your new functions (and maybe the odds calculator up top) to pick out which type of combination lock to choose.
A 3 section (0-9 per section, a 4 section, or a 39 digit rotary lock. Assume brute force hacking at 15 seconds per combination and worse-case scenario.

Next up is Fibonacci or Return to home page.

©2013 deveau enterprises