Basics: Factorial, Fibonacci, Algorithm, and Recursion

Basics: Factorial, Fibonacci, Algorithm, and Recursion

Our 1^st tutorial will focus on introductory mathematical functions in computer science & implementations.

J So let’s begin learning and don’t look back…

I’m sure everyone has heard of the factorial function by now which is denoted by,  n!

Definition # 1:

n! read “n factorial ,which in means “The product of the positive integers from 1 to N, inclusive…”  

("2000 Solved Problems In Discrete Mathematics" 101-110).

Side note: I copied this nice mathematical representation from Wikipedia. If I can’t find a nice graphical representation online than I will write in myself.

Examples & Questions:

5! = 5 * 4 * 3 * 2 * 1 = 120

10! = 10 * 9* 8* ….. * 1 = 3,628,800

The above definition states that for n=0 , the factorial function will return 1.

Therefore 0! =1.

And for n > 0 , then n multiplied by (n-1), recursively.

We will describe recursion soon in detail, it’s a very simple concept.

Definition # 2

Recursion is a function that calls or refers to itself.

Definition #3

Algorithm is a procedure for solving a mathematical problem (www.merriam-webster.com).

The word Algorithm is Latin name for Persian Arab mathematician Al-Khuwarizmi, who lived in ancient Persia, precisely modern day Iraq, he is also the founding father of Algebra. Algebra is also another Arabic word.

(http://www.encyclopedia.com/doc/1G2-2830902300.html).

Applications

Common use of factorials are in combinatorial analysis , such as combinations, permutations, binomial probability, etc.

Implementations in Java

The above implementation of the factorial function is based on the recursive definition, it is correct however naive, recursive functions tend to inefficient because they require previous recursive steps to be kept in memory and recalculated.  

The above implementation is an attempt at a more efficient “Algorithm”,however it is still recursive in nature because its needs to keep in “current memory” the previous step in order to compute current step.

This implementation is actually more efficient than previous recursive implementations. This time the previous factorial steps (j-1) are stored in array, and the current factorial is calculated by just accessing the results [j] = results[j-1] * j.

Now let’s go ahead and formally give definition for recursion.

Formal Definition of Recursion

A function is said to be recursive

1)      If there are certain base values, for which the function does not refer to itself.

2)      Every time the function refers to itself, the argument of the function must be closer to base value.

("2000 Solved Problems In Discrete Mathematics" 101-110).

You can easily see that the factorial function in definition # 1 , conforms to the formal definition above.

Now, run any of the implementations above for n!=5,n!=10,n!=50, you can see that factorial functions grows very fast , exponentially.

Now let’s look at another popular function, the Fibonnaci Sequence

0,1,1,2,3,5,8,13,21,34,55,89,…

Definition #4 , Fibonnaci Sequence

If n =0  or n =1, then F_n = n.

If  n> 1, then F_n = F_n-2 + F_n-1

("2000 Solved Problems In Discrete Mathematics" 101-110).

Applications

Fibonacci sequence is witnessed in the natural world, such as braches of a tree and petals of some flowers, it used to model some biological growth.

Examples & Questions:

1)      What is 10^th number in the Fibonacci sequence ?  fib(10) = 34

2)      What is the 20^th Fibonacci sequence , or fib(20)? Well don’t tell you are going add 20 numbers together by hand, let’s solve this by implementing the Fibonacci sequences definition.

Solution & Implementation in Java

The above Java code is recursive method that computes the Fibonacci sequence.

The above code is the loop that controls term we want the computation to terminate. The variable “n” below determines what Fibonacci term you want calculated.

Fibonacci 20, is computed as 6765 by above method called fib().

3)      What is the 200^th Fibonacci sequence?  Plug in 200 in the implementation from Question 2 and see what happens? It looks like recursive implementation was “Algorithmically inefficient”, so let’s re-implement Fibonacci using iterative approach.

Solution & Implementation in Java

J I’ll bet you any amount, that with above implementation you will not be able to calculate even Fibonacci 50.

So what’s happening? Isn’t the Java code the correct implementation of the Fibonacci definition? YES, but it’s “not an efficient implementation”, many mathematical formulas although correct, maybe inefficient if implemented directly based on their definition alone.

This is where the field of Algorithm Analysis & Computer Science becomes paramount, by providing alternative Algorithms/formulas that can be used in compute real world problems.

I have mentioned the word “efficient” several times, however so far I have not defined the “efficiency” formally, we will do so shortly.

For now just think of inefficient Algorithms, as functions that don’t have enough power to return desired answers in reasonable amounts of time.

A more efficient Implementation Fibonacci implementation

Fibonacci 200 is returned a this huge number 4,845,216,997,073,187,469 in under 1 second!!!.

J Can we do even better?  YES, we will visit this problem later when, we have built more mathematical & computational muscle.

Side note: Don’t dismiss recursion as inefficient technique; recursion is a powerful mathematical tool; many problems are solved recursively.

So far we learned about some functions, learned al little about recursion, and implemented our Algorithms.

However, to proceed we need to provide more formal definitions “efficiency”, and mathematical techniques to compare Algorithms.

Our next tutorial will be about, “Rate of growth…”.

 Further self-practice

1)      Implement a recursive method/function that doubles its input k, n times

2)      Implement a method/function that graphically prints out Khawrazmi’s Triangle (a.ka. Pascal’s Triangle)

3)      Implement Ackermann function recursively

References

1.       2000 Solved Problems In Discrete Mathematics. 1st. New York: McGraw-Hill, 1992. 101-110. Print.

2.       A Primer on Recursion. http://amitksaha.wordpress.com.

3.       Cormen, Thomas, et al. Introduction To Algorithms. 2nd. MIT press, 2001.