iterative..
while (k != N) {
S += i;
k = i;
i += k;
}
just for reference.. a tail-recursive version.. which can easily be converted to iterative without much thought.
int fib (int N, int pre = 1, int cur = 1) {
if (N < 2) return cur;
else return (fib (N-1, cur, cur+pre);
}
tree-recursive..
int fib (int N) {
if (N < 2) return 1;
else return (fib (N - 1) + fib (N - 2));
}
the second one, tree-recursive, takes longer to compute for larger values of N and uses up more of the program stack. as you follow the program.. what'll happen is, fib (N - 1) will keep on getting called until the terminating condition, call that time 0. since N at time 0 is now defined, all the other N's can be computed.. the program unwinds the recursion, each step the second portion of the statement gets called, fib (N-2).. which goes through the same thing as fib (N-1). for large values of N, it becomes extremely redundant. what you'll get is a tree-like structure where there are always at least 2 branches identical to one another for N greater than 2.
with the first one, no computations are necessary once the terminating condition is met (N < 2).. once the answer is computed, the program steps out until it gets to the top.