递归：一次返回双倍电话

int f(int n){ 
    if (n==0 || n==1) 
    return 1; 
    else 
    return 2*f(n-1)+2*f(n-2); 
}

如果n = 3，您怎么看这个步骤？如果只有一个“2 * f（n-1）”，我会知道如何去思考，但有两个调用。谢谢！递归：一次返回双倍电话

来源

2017-09-16 Oros Tom

好消息是，你不必考虑这一点。电脑足够聪明，可以为你思考。如果你坐着一张纸和一支笔，你可以在这里合理地绘制2-3级递归，但这很快就失控了。从这样的优势中，没有什么可以获得真正有用的东西。也许你可能想花一些时间研究“通过归纳证明”的纯数学概念。一旦你对这个普遍主张感到满意，这样的事情将成为第二天性。 –

我认为在纸上手工做n = 3或甚至n = 5个初始案例会非常有用。或者，使用调试程序逐步完成，只需在进行时在纸上绘制函数调用。了解这里发生的事情非常重要。 – hyde

它的工作原理与您称为两种不同的功能 - 比如说，2 * g（n-1）+ 2 * h（n-2）'一样。递归函数没有什么特别之处。 – molbdnilo

调用图的n = 3，应是这样的：

=> 2*f(2)+2*f(1); 
=> 2*[2*f(1)+2*f(0)] + 2*f(1) 
=> 2*[2*1 + 2*1] + 2*f(1) 
=> 8 + 2*1 
=> 10

来源

2017-09-16 12:39:55 nullpointer

OT，Q.E.D.通常放置在演示的*结尾处*;） –

@Bob__没有太多的话要放在之前:) – nullpointer

如果你把这个在每步操作的一个方面你喜欢的东西：

int f(int n){ 
    return fcont1(n, n < 2); 
} 
int fcont1(int n, int nl2) { 
    if(nl2) { 
     return n; 
    } else { 
     return fcont2(n); 
    } 
} 
int fcont2(int nm1){ 
    return fcont3(n, n-1); 
} 
int fcont3(int n, int nm1){ 
    return fcont4(n, f(nm1)); 
} 
int fcont4(int n, int r1){ 
    return fcont5(r1, n-2); 
} 
int fcont5(int r1, int nm2){ 
    return fcont6(r1, f(nm2)); 
} 
int fcont6(int r1, int r2) { 
    return fcont7(2*r1, r2); 
} 
int fcont7(int dr1, int r2) { 
    return fcont7(dr1, 2*r2); 
} 
int fcont7(int dr1, int dr2) { 
    return dr1+dr2; 
}

这个重写最后使用了更多的mem因为C没有优化尾部调用，但任何执行此操作的语言都与所决定的操作顺序完全相同。

来源

2017-09-16 16:13:23 Sylwester

递归：一次返回双倍电话

回答

相关问题