理解此递归的难点

我没有在C++中获得这种递归练习。那就是：理解此递归的难点

int fatt(int x){ 
    int s=1; // here. since 's' will always be 1 shouldn't i get 1 as an output??? 
    if(x>1) { s = x*fatt(x-1); } 
    return s; 
} 

int main() 
{ 
    int n; 
    cout << "Type a number: "; 
    cin >> n; 
    if (n < 0) { cout << "Error" << endl; } 
    if (n <=1) { cout << "Factorial: 1" << endl; } 
    else { cout << "Factorial: " << fatt(n) << endl; } 
}

如果我把它s=0返回我作为一个输出总是0，如果我把2 O.o我不明白它是如何工作双打的结果。据我所知，x总是会减少，直到达到2，并且返回结果，但每次调用该函数都不应得到1的值。

来源

2016-06-14 user2580684

“不应该给'1的值”是的，但下一行将's'分配别的东西，所以不，它并不总是返回1. – tkausl

当你调用fatt（3）时，x不会改变。 fatt（3）的执行调用fatt（2），用另一个变量x创建一个新的上下文，但是不同。 –

递归的可视化有时会有所帮助：http://www.mrlamont.com/uploads/1/7/0/2/17021682/factorial.png – eol

说你打电话与参数值3的功能：它是这样的：

int fatt(3) { 
    int s = 1; 
    if (3 > 1) s = 3 * fatt(3 - 1); 
    return s; 
}

所以s是calulation 3 * fatt(2)和fatt(2)结果的结果是：

int fatt(2) { 
    int s = 1; 
    if (2 > 1) s = 2 * fatt(2 - 1); 
    return s; 
}

所以s是计算结果2 * fatt(1)和fatt(1)的结果是：

int fatt(1) { 
    int s = 1; 
    if (1 > 1) s = 1 * fatt(1 - 1); // False so this is never executed. 
    return s; 
}

的fatt(1)的结果为1。所以这就是我们回归到fatt(2)通话，然后转化为：

s = 2 * 1;

这给结果2，然后返回到fatt(3)电话，然后给：

s = 3 * 2;

哪个给出结果6.

记住，局部变量s是堆栈上的每个时间推该函数是EXECUT编辑。所以它不是同一个变量。

如果您将s初始化为2，则第一行将显示为：s = 2 * 2;，其余的函数将使结果中的值增加一倍。由于s确实是您最终乘以的因子，因子为：

因此，序列：3 * 2 * 1变为3 * 2 * 2。

来源

2016-06-14 08:37:10

的结果非常感谢！我终于明白了。我应该仔细看过每一步，我会理解它。 – user2580684

变量s对函数fatt的给定实例是本地的。由于函数本身递归调用，所以每个调用都会获得自己的新副本s。这会初始化为1，但不会影响堆栈中所有先前的s实例。然后将它们中的每一个都乘以x的本地副本后，调用fatt调用的结果。

来源

2016-06-14 08:36:39 Smeeheey

为什么's'倍增？我没有看到任何乘法，'s'之前有'='？ – user2580684

我编辑了答案，因为它不是很清楚。每个本地's'被分配给（'s'，由下次调用计算）*'x'。所以's'被乘以下一次调用的结果，即'fatt（x-1）' – Smeeheey

's'应该是1，但它被赋值，然后在函数完成时更改其保留的值。

递归可能有点难以理解，但一旦你做了，它很漂亮。

我建议你使用笔和纸。

1）令x = 3;

int fatt(3) { 
    int s = 1; 
    if (3 > 1) s = 3 * fatt(3 - 1); 
    return s;}

2）在功能3> 1 =真，从而它被再次传递，但此时如（3-1），即2

注：功能未完成执行

3）现在X = 2

int fatt(2) { 
    int s = 1; 
    if (2 > 1) s = 2 * fatt(2 - 1); 
    return s;}

4）重复步骤2）（2-1），即1

5）由于x在第三函数的IS NOT> 1 N通话这导致S的恢复

s = 1; 
return s;

所以......

在2RD函数调用开始：

s = x * fatt(x-1); 
s = 2 * 1; 
return s;

重复此再次为第一次调用）

s = x * fatt(x-1); 
s = 3 * 2; 
return s;

认为它像一堆功能

第一堆叠-------调用堆2和等待

第二堆----------呼叫叠加3并等待

第一堆栈------- ---等待

最后...

3堆----------条件没有得到满足的回报

第二堆----------条件完成返回

1st st ack --------- condition done return

希望能帮到

来源

2016-06-14 09:16:11 Twahanz

理解此递归的难点

回答

相关问题