Always two there are, a master and an apprentice. -yoda
Monday, November 22, 2010
[DSA] Iteration and recursion
Look into the mirror and observe your self. Look into your eyes, you will notice that in your pupil (the dark/blue/green color portion of the eye if you are asian/Caucasian) you can see yourself in it. Now, look into that pupil on the mirror. You will observe yourself again, albeit a scaled version. That is what i call recursion, you will see yourself again and again in your pupil.
Assume that you can see even the smallest detail of yourself through the mirror, notice that there is no end to the vision?
This is not good for recursion in computer science/programming. The program keeps executing recursively, until the system resources run out. So, at least a condition for the recursion to stop must be defined, which what we called the base case.
Anything that is solved iteratively, can be solved recursively.
Fibonacci The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself. Once the formula is established, it is easy to figure out the code.
Fibonacci is a natural candidate for recursion, because it need to use data that are computed before in that particular series. Hence, we need to store this temporary data somewhere. In recursion, temporary data is stored on the stack.
1. Write a iteration fuction that calculates 2^n. 2 to the power of n. n being the input from cin.
2. Write a recursive function that calculates 2^n. n being the input from cin.
3. when n is very large, what are the parameters need to take into considerations?
4. What do you observed for the 1. and 2. when n is very large?
5. Is 2^n a natural candidate for recursion??