用迭代代替递归

Question

我有一个递归函数，我需要将其转换为迭代函数，但我完全卡住了。谁能帮助我或指出正确的方向？

f :: Int -> Int
f(0) = 5
f(1) = 8
f(2) = 3
f(n) = (f(n-3)) * (f(n-1))

干杯

Answer 1

下面的代码片段应该可以解决问题：

int output[1000];
output[0] = 5;
output[1] = 8;
output[2] = 3;

for (int i=3; i < 1000; ++i) {
    output[i] = output[i-3] * output[i-1];
}

奖励：以这种方式非递归地实现你的函数被称为动态规划。

Answer 2

这看起来行得通。本质上它会保留最近的 3 个数字并向上移动直到我们命中 n.

public int rf(int n) {
    return n == 0 ? 5
            : n == 1 ? 8
                    : n == 2 ? 3
                            : rf(n - 3) * rf(n - 1);
}

public int nrf(int n) {
    int[] v = {5, 8, 3};
    int x = n == 0 ? 5
            : n == 1 ? 8
                    : n == 2 ? 3
                            : 0;
    for (int i = 2; i < n; i++) {
        x = v[0] * v[2];
        v[0] = v[1];
        v[1] = v[2];
        v[2] = x;
    }
    return x;
}

public void test() {
    for (int i = 0; i < 10; i++) {
        System.out.println(rf(i) + " = " + nrf(i));
    }
}

正确打印：

5 = 5
8 = 8
3 = 3
15 = 15
120 = 120
360 = 360
5400 = 5400
648000 = 648000
233280000 = 233280000
1286582272 = 1286582272

用迭代代替递归

Replacing recursion with iteration

iteration

algorithm

recursion