问递归-我不明白它是如何工作的。
EN

Stack Overflow用户

提问于 2021-04-01 23:18:39

回答 4查看 79关注 0票数 0

我无法理解递归函数的一些内容。假设我在计算x数的阶乘。代码将如下所示：

#include <iostream>
using namespace std;

int factorial(int y){
    if(y == 0)
        return 1;
    return y * factorial(y-1);


}

int main() {
    int n;
    cin >> n;
    cout << factorial(n);



    return 0;
}

在这里，据我理解，我有一个基本的例子，它会在某一时刻停止这个函数。很好，直到现在，在大小写之后，下一个语句将返回x*阶乘(x-1)。假设我们想要找到数字"4“的阶乘。看起来会是这样的：

x = 5 --> x != 0, return 5 * factorial(4) | 
x = 4 --> x != 0, return 4 * factorial(3) | 
x = 3 --> x != 0, return 3 * factorial(2) |
x = 2 --> x != 0, return 2 * factorial(1) |
x = 1 --> x != 0, return 1 * factorial(0) |

现在，由于x等于0，下一个语句将运行：

if(x == 0)
  return 1;

我不明白的是:如果函数返回1，程序应该准确地返回数字"1"，为什么以及如何返回递归语句计算出来的内容。

c++

recursion

人脸识别特惠活动

精准实时的人脸检测、分析、识别等服务，在线、离线满足多样需求，可应用于智慧零售、智慧社区、在线娱乐等多种应用场景

回答 4

Stack Overflow用户

回答已采纳

发布于 2021-04-01 23:35:37

1) x = 5 --> x != 0, return 5 * factorial(4) | 
2) x = 4 --> x != 0, return 4 * factorial(3) | 
3) x = 3 --> x != 0, return 3 * factorial(2) |
4) x = 2 --> x != 0, return 2 * factorial(1) |
5) x = 1 --> x != 0, return 1 * factorial(0) |

阶乘(0)将返回1；因此，第5行将如下：

x = 1 --> x != 0, return 1 * 1 x，它是factorial(1)

factorial(1)将返回1；因此，第4行将如下所示：

x = 2 --> x != 0, return 2 * 1 x，它是factorial(2)

factorial(2)将返回2；因此第3行将如下所示：

x = 3 --> x != 0, return 3 * 2 x，它是factorial(3)

factorial(3)将返回6；因此，第2行将如下所示：

x = 4 --> x != 0, return 4 * 6 x，它是factorial(4)

factorial(4)将返回24；因此，第1行将如下所示：

x = 5 --> x != 0, return 5 * 24 = 120

票数 1

Stack Overflow用户

发布于 2021-04-01 23:53:06

如果需要，可以向代码中添加更多的可视化信息，以使流程在输出中更加可见。

#include <iostream>
using namespace std;

void indent(int y) {
    for (int i = 0; i < y; ++i) {
        std::cout << "  ";
    }
}

int factorial(int y, int max){
    indent(max - y);
    std::cout << "calling factorial(" << y << ")" << std::endl;

    if(y == 0) {
        indent(max - y);
        std::cout << "returns 1" << std::endl;
        return 1;
    }
    auto ret = y * factorial(y-1, max);
    indent(max - y);
    std::cout << "returns " << ret << std::endl;
    return ret;


}

int factorial(int y) {
    return factorial(y, y);
}

int main() {
    // int n;
    // cin >> n;

    for (int n = 0; n < 5; ++n) {
        std::cout << "\nstart\n";
        cout << factorial(n) << std::endl;
    }

    return 0;
}

start
calling factorial(0)
returns 1
1

start
calling factorial(1)
  calling factorial(0)
  returns 1
returns 1
1

start
calling factorial(2)
  calling factorial(1)
    calling factorial(0)
    returns 1
  returns 1
returns 2
2

start
calling factorial(3)
  calling factorial(2)
    calling factorial(1)
      calling factorial(0)
      returns 1
    returns 1
  returns 2
returns 6
6

start
calling factorial(4)
  calling factorial(3)
    calling factorial(2)
      calling factorial(1)
        calling factorial(0)
        returns 1
      returns 1
    returns 2
  returns 6
returns 24
24