fibonacci series is defined as: f(n) = n for 0 <= n <= 1 f(n) = f(n-1) + f(n-2) ============= O(2^n) unusable. Inefficiency comes from that fact that same fibonacci number needs to be calculated again and again. If you trace the algorithm for n=4,5,6 etc. you would know how. /* for(int i=0; i < 10; i++) System.out.println(fib1(i)); */ int fib1(int n){ if ( n <= 1 ){ return n; } else { return fib1(n-1) + fib1(n-2); } } ============= storing series in an array and get previous values from array /* int[] fn = fib3[10]; for(int i=0; i < fn.length; i++) System..out.println(fn[i]); */ int[] fib3(int n){ int[] ret = new int[n]; for(int i=0; i < n; i++){ if(i <= 1){ ret[i] = i; } else { ret[i] = ret[i-1] + ret[i-2]; } } return ret; } =============== actually we need to store only last 2 items from the series not all the numebrs void fib4(int n){ int prev_2=0, prev_1=1; // n-2 and n-1 for(int i=0; i < n; i++){ if(i <= 1){ System.out.println(i); } else { int x = prev_1 + prev_2; // n = (n-1) + (n-2) System.out.println(x); prev_2 = prev_1; // n-2 = n-1 prev_1 = x; // n-1 = n } } } ================= and some people might write like which is no very obvious and intuitive to me, I prefer "fib4" function. void fib2(int n){ int f = 0; int g = 1; for(int i=0; i < n; i++){ System.out.println(f); f = f + g; g = f - g; } }

Advertisements