Thursday, May 21, 2015

Simple example of Recursion vs Iteration

Recursion example:
Question: there are n stairs, each time one can climb 1 or 2. How many different ways to climb the stairs.
Step 1: Finding the relationship before n and n-1.
To get n, there are only two ways, one 1-stair from n-1 or 2-stairs from n-2. If f(n) is the number of ways to climb to n, then f(n) = f(n-1) + f(n-2)
Step 2: Make sure the start condition is correct.
f(0) = 0;
f(1) = 1;
public static int f(int n){
 if(n <= 2) return n;
 int x = f(n-1) + f(n-2);
 return x;
}
The time complexity of the recursive method is exponential to n. There are a lot of redundant computations.
f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(2) + f(2) + f(1)
It should be straightforward to convert the recursion to iteration.
public static int f(int n) {
 
 if (n <= 2){
  return n;
 }
 
 int first = 1, second = 2;
 int third = 0;
 
 for (int i = 3; i <= n; i++) {
  third = first + second;
  first = second;
  second = third;
 }
 
 return third;
}
See also

Example of Tail Recursion

Popular Posts