将迭代转换为递归

Question

正在观看此视频作者：Anton Spraul：https://www.youtube.com/watch?v=oKndim5-G94&index=4&list=PLKQ5LYb497AZIZe9dBWy8GwLluVaMQVj0，其中他谈到通过使用迭代函数和调度函数来解决递归问题。我试图通过使用相同的方法找到第n个fibonnaci数，但问题是他在调度程序中使用数组的结束值，在我的情况下是空的。这就是我想要做的：

//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);

对于Fibonacci序列：

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

Answer 2

这根本不能解答您的问题，但您可能对如何使用多次递归解决此问题感兴趣：

private int fib(int no)
{
    if (no <= 1)
        return no;

    return fib(no - 1) + fib(no - 2);
}