Поверните рекурсивную функцию в итеративную версию

Question

Мне нужно превратить следующий рекурсивный код в итеративную версию, и мой разум обжарен. я чувствую, что я теряю что-то очевидное. любая помощь приветствуется.

public static int computeRecursive(int n){ 
    if(n <= 1){ 
     return n; 
    } 
    else{ 
     return 2 * computeRecursive(n-2) + computeRecursive(n-1); 
    } 
} 

Answer 1

Возможно, вы пытаетесь использовать приведенный ниже код. Он похож на ряд фибоначчи.

public static int computeRecursive(int n){ 
int a[]=new int[n]; 
a[0]=1; a[1]=1; 
for(int i=2;i<n;i++){ 
    a[i]=2*a[i-2]+a[i-1]; 
} 
return a[n-1]; 
} 

Answer 2

Это похоже на итерационный ряд Фибоначчей, где вы держите начальных два значения вашей функции f() два переменных a и b. Затем вычислить результат для текущего N прочь этих двух предыдущих результатов:

public static int f(int n) { 
    if (n <= 1) { 
     return n; 
    } 

    int result = 0; 
    int a = 0, // f(0) = 0 
     b = 1; // f(1) = 1 

    // start iteration at n=2 because we already have f(0) and f(1) 
    for(int i = 2; i <= n; i++) { 
     // f(n) = 2 * f(n-2) + f(n-1) 
     result = 2 * a + b; 

     // f(n-2) = f(n-1) 
     a = b; 
     // f(n-1) = f(n) 
     b = result; 
    } 

    return result; 
} 

Answer 3

На мой взгляд, как рекурсивные и итеративные решения являются слабыми, если вы можете просто применить свои навыки математика и выработать формулу.

В этом случае мы имеем: f (n) = (2 ** n - (- 1) ** n)/3. Пыль, как вы его работаете.

f(0) = 0 
f(1) = 1 
f(n) = f(n-1) + 2 * f(n-2) 

So the polynomial for this recurrence is: 
r ** 2 = r + 2 

If you sole that you will get the values of r as r1 =−1 and r2 =2 

So the solution to the recurrence is on the form: 
f(n) = c1 ∗ r1 ** n + c2 ∗ r2 ** n 

To work out the values for c1 and c2 constants just use the initial condition f(0) = 0 and f(1) = 1 and you will get 
c1 = -1/3 and c2 = 1/3 

So the final formula for your iteration is 
f(n) = (-1 * (-1) ** n + 2 ** n)/3 = (2 ** n -(-1) ** n)/3. 

Как только вы знаете, что формула, реализующая ее в java или на любом другом языке, проста.

public static int f(int n) { 
    return n <= 1 ? n: (Math.pow(2,n) - Math.pow(-1, n))/3; 
} 

Надеется, что это помогло