   Recursive and iteration
  Hi, a need some help on this. I need to use the recursive version to create an iteration version but I just cant get it right...Thanks you!#include <iostream>using namespace std;int recusion(int);int iteration(int);int main (){int n;cout << "Enter a integers: ";cin >> n;cout << recusion(n);cout << endl;cout << iteration(n);cout << endl;}int recusion(int n){if(n == 1)return 3;else if(n == 2)return 2;elsereturn recusion(n - 2) + recusion(n - 1);}int iteration(int n){int pCur = 0;int pNext = 0;int pOld = 0;int i = 2;while(i <= n){if(i == 1){pNext += 3;pCur = 3;if (n == 1)return pCur;}else if(i == 2){pNext += 2; pCur = 2;if (n == 2)return pCur;} elsepNext = pCur + pOld;pOld = pCur;pCur = pNext; i++;}return pCur;} [Edited by - Zahlman on November 20, 2010 2:30:12 AM]
Quote:Original post by TongieI need to use the recursive version to create an iteration versionWhat does that even mean?;  I think he means he needs to change a recursive function into a non-recursive function.   ;  Well it's doubly-recursive, not simply tail-recursive so it's not as straightforward as converting the recursion into a loop.However by recognising that it is simply a variation of the fibonacci sequence, one can easily convert it to an iterative function.please use [source][/source] tags around your code.   ;  The first step is to identify what the recursive function is doing. In this case, it is returning the sum of itself being called on n-1 and n-2. Since we have two base cases, we know we're looking at a recursive sum function.Please look up http://en.wikipedia.org/wiki/Fibonacci_number   ;  This is very easy:int iteration(unsigned n) {  int a = 1, b = 0, x = 0, y = 1;  for (; n; n >>= 1) {    if (n & 1) { int t = a*x + b*y; b = a*y + b*(x + y); a = t;    }    int t = x*x + y*y;    y = x*y + y*(x + y);    x = t;  }  return 3*b - a;}