给出一个函数的本伪code

Given this pseudo code of a function

f(0) = 1; 
f(1) = 3; 
f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2.

是否有这样做的非递归的方式？

Is there a non recursive way of doing this?

推荐答案

是的，所有的递归算法可以转化为迭代的。递归解决您的问题是一样的东西（假code）：

Yes, all recursive algorithms can be converted into iterative ones. The recursive solution to your problem is something like (pseudo-code):

def f(n):
    if n == 0: return 1
    if n == 1: return 3
    return 3 * f(n-1) - f(n-2)

既然你只需要记住previous两个词来计算当前，您可以使用类似下面的伪code：

Since you only have to remember the previous two terms to calculate the current one, you can use something like the following pseudo-code:

def f(n):
    if n == 0:
        return 1
    if n == 1:
        return 3
    grandparent = 1
    parent = 3
    for i = 2 to n:
        me = 3 * parent - grandparent
        grandparent = parent
        parent = me
    return me

这只是处理递归终止条件第一然后遍历它通常会调用自身。在每次迭代中，你计算的当期，然后旋转通过祖父母和父母的条件。

This simply handles the "recursive" termination condition first then iterates where it would normally call itself. At each iteration, you calculate the current term, then rotate the terms through the grandparent and parent.

有没有必要保持祖父母身边，一旦你计算出当前迭代，因为它不再被使用。

There is no need to keep the grandparent around once you've calculated the current iteration since it's no longer used.

在事实上，可以说，该迭代求解是更好（从性能观点来看），因为术语不重新计算，因为它们是在递归溶液。该递归解决方案的确实的有一定的优雅这件事，但（递归解决方案通常做的）。

In fact, it could be said that the iterative solution is better (from a performance viewpoint) since terms are not recalculated as they are in the recursive solution. The recursive solution does have a certain elegance about it though (recursive solutions generally do).

当然，像Fibonacci序列，即珍惜你计算起来非常快，因此，如果你想要的是可能是最快的解决方案（你应该检查所有的性能要求，包括我），一个pre计算的查找表可能是的路要走。

Of course, like the Fibonacci sequence, that value you calculate rises very quickly so, if you want what's possibly the fastest solution (you should check all performance claims, including mine), a pre-calculated lookup table may be the way to go.

使用下面的Java code创建长值表（即，而的条件只是一个偷偷摸摸的伎俩赶上溢出，这是在哪个点你可以停止建造阵列）：

Using the following Java code to create a table of long values (that while condition is just a sneaky trick to catch overflow, which is the point at which you can stop building the array):

class GenLookup {
    public static void main(String args[]) {
        long a = 1, b = 3, c;
        System.out.print ("long lookup[] = { " + a + "L, " + b + "L");
        c = 3 * b - a;
        while ((c + a) / 3 == b) {
            System.out.print (", " + c + "L");
            a = b; b = c; c = 3 * b - a;
        }
        System.out.println (" };");
    }
} 

给你，你可以直接插上去查找函数，一个数组的定义按照下面的例子：

gives you an array definition that you can just plug in to a lookup function, as per the following example:

public static long fn (int n) {
    long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
        17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
        14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
        1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
        225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
        10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
        498454011879264L, 1304969544928657L, 3416454622906707L,
        8944394323791464L, 23416728348467685L, 61305790721611591L,
        160500643816367088L, 420196140727489673L, 1100087778366101931L,
        2880067194370816120L, 7540113804746346429L };

    if ((n < 1) || (n > lookup.length))
        return -1L;

    return lookup[n-1];
}

有趣的是，WolframAlpha的想出了甚至不使用迭代一个公式化的方法。如果你去他们的网站并输入 F（0）= 1，F（1 ）= 3，F（N）= 3F（N-1）-f（N-2），你会得到的公式：

Interestingly enough, WolframAlpha comes up with a formulaic approach that doesn't even use iteration. If you go to their site and enter f(0)=1, f(1)=3, f(n)=3f(n-1)-f(n-2), you'll get back the formula:

不幸的是，它可能无法以最快的速度迭代，给定的输入值的数量有限导致的东西，可以适合在一个Java 长，因为它使用浮点。这几乎肯定是（但同样，你需要检查这）不是一个查找表慢。

Unfortunately, it may not be as fast as the iteration, given the limited number of input values that result in something that can fit in a Java long, since it uses floating point. It's almost certainly (but, again, you would need to check this) slower than a table lookup.

和，它在数学，其中像非无限的存储现实世界的界限不发挥作用，但是，这可能是由于IEEE precision的限制，这世界也许完美的，它打破了在更高的价值 N 。

And, it's probably perfect in the world of maths where real-world limits like non-infinite storage don't come into play but, possibly due to the limits of IEEE precision, it breaks down at higher values of n.

以下功能是那个EX pression相当于和查找解决办法：

The following functions are the equivalent of that expression and the lookup solution:

class CheckWolf {
    public static long fn2 (int n) {
        return (long)(
            (5.0 - 3.0 * Math.sqrt(5.0)) *
                Math.pow(((3.0 - Math.sqrt(5.0)) / 2.0), n-1) +
            (5.0 + 3.0 * Math.sqrt(5.0)) *
                Math.pow(((3.0 + Math.sqrt(5.0)) / 2.0), n-1)
            ) / 10;
    }

    public static long fn (int n) {
        long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
            17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
            14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
            1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
            225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
            10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
            498454011879264L, 1304969544928657L, 3416454622906707L,
            8944394323791464L, 23416728348467685L, 61305790721611591L,
            160500643816367088L, 420196140727489673L, 1100087778366101931L,
            2880067194370816120L, 7540113804746346429L };
        if ((n < 1) || (n > lookup.length)) return -1L;
        return lookup[n-1];
    }

现在我们需要一个主线对它们进行比较：

Now we need a mainline to compare them:

    public static void main(String args[]) {
        for (int i = 1; i < 50; i++)
            if (fn(i) != fn2(i))
                System.out.println ("BAD:  " + i + ": " + fn(i) + ", " + fn2(i)
                    + " (" + Math.abs(fn(i) - fn2(i)) + ")");
            else
                System.out.println ("GOOD: " + i + ": " + fn(i) + ", " + fn2(i));
        }
    }

这将输出：

GOOD: 1: 1, 1
GOOD: 2: 3, 3
GOOD: 3: 8, 8
GOOD: 4: 21, 21
GOOD: 5: 55, 55
GOOD: 6: 144, 144
GOOD: 7: 377, 377
GOOD: 8: 987, 987
GOOD: 9: 2584, 2584
GOOD: 10: 6765, 6765
GOOD: 11: 17711, 17711
GOOD: 12: 46368, 46368
GOOD: 13: 121393, 121393
GOOD: 14: 317811, 317811
GOOD: 15: 832040, 832040
GOOD: 16: 2178309, 2178309
GOOD: 17: 5702887, 5702887
GOOD: 18: 14930352, 14930352
GOOD: 19: 39088169, 39088169
GOOD: 20: 102334155, 102334155
GOOD: 21: 267914296, 267914296
GOOD: 22: 701408733, 701408733
GOOD: 23: 1836311903, 1836311903
GOOD: 24: 4807526976, 4807526976
GOOD: 25: 12586269025, 12586269025

看起来不错了这里，多了一些：

Looking good up to here, some more:

GOOD: 26: 32951280099, 32951280099
GOOD: 27: 86267571272, 86267571272
GOOD: 28: 225851433717, 225851433717
GOOD: 29: 591286729879, 591286729879
GOOD: 30: 1548008755920, 1548008755920
GOOD: 31: 4052739537881, 4052739537881
GOOD: 32: 10610209857723, 10610209857723
GOOD: 33: 27777890035288, 27777890035288
GOOD: 34: 72723460248141, 72723460248141
GOOD: 35: 190392490709135, 190392490709135
GOOD: 36: 498454011879264, 498454011879264

但后来事情开始行不通了：

But then something starts going awry:

BAD:  37: 1304969544928657, 1304969544928658 (1)
BAD:  38: 3416454622906707, 3416454622906709 (2)
BAD:  39: 8944394323791464, 8944394323791472 (8)
BAD:  40: 23416728348467685, 23416728348467705 (20)
BAD:  41: 61305790721611591, 61305790721611648 (57)
BAD:  42: 160500643816367088, 160500643816367232 (144)
BAD:  43: 420196140727489673, 420196140727490048 (375)

这以上是着急接近，并且该数字在错误的数量是成比例的，在结果的位数的事实，表明它可能是一个损失OF- precision问题

The fact that the above are tantalisingly close, and that the number of digits in the error is proportional to the number of digits in the result, indicates it's probably a loss-of-precision problem.

这点之后，公式化的功能只是开始返回的最长时间值：

After this point, the formulaic function just starts returning the maximum long value:

BAD:  44: 1100087778366101931, 922337203685477580 (177750574680624351)
BAD:  45: 2880067194370816120, 922337203685477580 (1957729990685338540)
BAD:  46: 7540113804746346429, 922337203685477580 (6617776601060868849)

然后我们查找功能分解，以及因为这些数字太大了很久：

And then our lookup function breaks down as well since the numbers are too big for a long:

BAD:  47: -1, 922337203685477580 (922337203685477581)
BAD:  48: -1, 922337203685477580 (922337203685477581)
BAD:  49: -1, 922337203685477580 (922337203685477581)