正在观看 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;
}
我知道迭代函数可以直接工作,但我想做的是使用视频中的方法将其转换为递归函数。
最佳答案
用递归代替迭代的一般方案是:
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
关于algorithm - 将迭代转换为递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49062923/