algorithm - 将迭代转换为递归

Question

正在观看 Anton Spraul 的这段视频: https://www.youtube.com/watch?v=oKndim5-G94&index=4&list=PLKQ5LYb497AZIZe9dBWy8GwLluVaMQVj0其中他谈到通过使用迭代函数和调度函数来解决递归问题。我试图通过使用相同的方法找到第 n 个斐波那契数，但问题是他使用了调度程序中数组的最终值，在我的例子中这些值是空的。这就是我想要做的:

//n is the nth fibonnaci number to be found.
int fibonacci(int fiboarray[], int number)
{
    int i = 2;
    for (i = 2; i < number; i++)
    {
        fiboarray[i] = fiboarray[i - 1] + fiboarray[i - 2];
    }

    return fiboarray[i - 1];
}
int fibonaccidispatcher(int fiboarray[], int number)
{
    if(number==0)return 0;
    int last=fiboarray[number-1]+fiboarray[number-2];
    fiboarray[number]=fibonaccidispatcher(fiboarray,number-1)+last;
    return fiboarray[number];


    // return diff;
}

我知道迭代函数可以直接工作，但我想做的是使用视频中的方法将其转换为递归函数。

Answer 1

用递归代替迭代的一般方案是:

for (int i=0; i<N; i++) {
    // some computation with i
}

可以替换为:

void f(int i,int N) {
  if (i==N) return;
  // some computation with i
  f(i+1);
}
...
f(0,N);

假设您正在计算阶乘:

fact = 1;
for (int i=1; i<=N; i++) {
    fact = fact*i;
}

这可以替换为:

int fact = 1;
void fact(int i,int ?) {
    if (i>N) return;
    fact = fact*i;
    fact(i+1);
}
...
fact(1,N);

对于斐波那契数列:

int fib = 0;
int fib1 = 1;
int fib2 = 1;

for (int i=2; i<=N; i++) { // general case, needs to test for case 1 and 2...no really important
    fib = fib1+fib2;
    fib2 = fib1;
    fib1 = fib;      
}

递归版本是:

int fib = 0;
int fib1 = 1;
int fib2 = 1;

void fib(int i,int N) {
    if (i>N) return;
    fib = fb1+fib2;
    fib2 = fib1;
    fib1 = fib;
    fib(i+1,N);
}
...
fib(2,N);

现在如果你想避免全局变量，你可以这样写:

int fib(int basecase1, int basecase2, int i, int N) {
    if (i==1) return basecase1;
    if (i==2) return basecase2;
    if (i>=N) return basecase1;
    return fib(basecase1+basecase2, basecase1, i+1, N);
}
...
int result = fib(1,1,1,N);

对于调用 fib(1,1,1,5) 你将有:

1 1 1 5
2 1 2 5
3 2 3 5
5 3 4 5
8 5 5 5
--> 8