(page 101(2))
|
|
(page 101(2)) |
|
| The Factorial: A Recursive definition | |||||
|
Ever thought of just multiplying the numbers as in:
1 = 1 1 × 2 = 2 1 × 2 × 3 = 6 1 × 2 × 3 × 4 = 24 1 × 2 × 3 × 4 × 5 = 120 1 × 2 × 3 × 4 × ... × N = ?These numbers get pretty big pretty fast but are very useful in certain branches of mathematics. In fact they are so important that we have a special way of writing them or a notation for them, as writing out 1×2×3×... gets very tedious. What we use is the `!' sign after the number, so: 1 × 2 × 3 = 3! 1 × 2 × 3 × 4 × ... × N = N!and it is pronounced N factorial. As an example of its use: What is the number of ways you can order the four letters 'A', 'B', 'C', and 'D'? There are 4 ways to choose the first letter, then 3 ways left to choose the second, 2 ways to choose the third, and 1 way to choose the fourth, making the number of choices 4 × 3 × 2 × 1, or 4 factorial which is 24. How many 5 card poker hands are there? 52 factorial divided by 5 factorial times (52-5) factorial 52! ÷ ( 5! × 47!) = 2,598,960How do we define factorial? Recursively!! 0! = 1 N! = N × (N-1)! for N > 0
Euclid's Algorithm: A Recursive Function |
In the 4th century B.C.E., a Greek called Euclid created what is
thought to be the first algorithm. It calculates the Greatest Common
Divisor (the GCD) of two numbers.
The Greatest Common Divisor is sometimes called the
Greatest Common Factor.
The GCD for two numbers, both
of which cannot be zero, is the largest number that
evenly divides both numbers.
| For example, the GCD of 24 and 36 is 12 since 12 is the largest number that divides both 24 and 36, and the GCD of 25 and 36 is 1, because there's no larger number that divides both 25 and 36. Usually it is written out in instructions that are repeated until the answer is reached, but we can also write it recursively. We'll only consider numbers greater than or equal to zero at this time. The GCD of A and B or GCD (A , B) is: I) if A and B are both zero, then GCD (A , B) is undefined. II) if A is zero, GCD(A , B) is B III) if B is zero, GCD(A , B) is A IV) otherwise and here comes the recursive bit GCD(A , B) is GCD(B , (A modulus B) )Note that (A modulus B) is the remainder when A is divided by B. Let's run the algorithm for our two examples: GCD(36 , 24) = GCD(24 , 36 modulus 24) applying the recursion = GCD(24 , 12) 36 modulus 24 is 12 = GCD(12, 24 modulus 12) applying the recursion again = GCD(12, 0) 24 modulus 12 is 0 = 12 applying Step III GCD(36 , 25) = GCD(25, 36 modulus 25) = GCD(25, 11) 36 modulus 25 is 11 = GCD(11, 4) = GCD(4, 11 modulus 4) = GCD(4, 3) = GCD(3, 4 modulus 3) = GCD(3, 1) = GCD(1, 3 modulus 1) = GCD(1, 0) = 1 by step III There you go -- a 2400 year old use of recursion. | ||
| hanoi05.qh - 1.6 - 05/10/04 |
|