C++ 阶乘程序中的递归

Recursion in c++ Factorial Program

提问by uill kk

hello i have this piece of code that i coded based on some other recursion and factorial programs but my problem is that i am really confused as to how it stored the value and kept it and then returned it at the end

你好，我有一段基于其他递归和阶乘程序编码的代码，但我的问题是我真的很困惑它如何存储值并保留它然后在最后返回它

int factorialfinder(int x)
{
    if (x == 1)
    {
        return 1;
    }else
    {
        return x*factorialfinder(x-1);
    }
}
int main()
{
  cout << factorialfinder(5) << endl;
}

so 5 goes in, and gets multiplied by 4 by calling its function again and again and again, then it gets to one and it returns the factorial answer

所以 5 进入，并通过一次又一次地调用它的函数乘以 4，然后它得到 1 并返回阶乘答案

why? i have no idea how it got stored, why is return 1 returning the actual answer, what is it really doing?

为什么？我不知道它是如何存储的，为什么 return 1 返回实际答案，它到底在做什么？

回答by JNL

Source: Image is taken from: IBM Developers website

来源：图片取自：IBM 开发人员网站

Just take a look at the picture above, you will understand it better. The number never gets stored, but gets called recursively to calculate the output.

看看上面的图片，你会更好地理解它。该数字永远不会被存储，而是被递归调用以计算输出。

So when you call the fact(4) the current stack is used to store every parameter as the recursive calls occur down to factorialfinder(1). So the calculation goes like this: 5*4*3*2*1.

因此，当您调用 fact(4) 时，当前堆栈用于存储每个参数，因为递归调用发生到 factorialfinder(1)。所以计算是这样的：5*4*3*2*1。

int factorialfinder(int x)         
{
    if (x == 1)        // HERE 5 is not equal to 1 so goes to else
    {
        return 1;
    }else
    {
        return x*factorialfinder(x-1); // returns 5*4*3*2*1  when x==1 it returns 1
    }
}

Hope this helps.

希望这可以帮助。

回答by maditya

Return 1 is not returning the actual answer. It's just returning the answer to calling

返回 1 不返回实际答案。它只是返回呼叫的答案

factorialfinder(1);

which happens in your code.

这发生在您的代码中。

In any program, a call stack is a space in memory that is used to keep track of function calls. Space from this memory is used to store the arguments to a function, as well as the return value of that function. Whenever some function A calls another function B, A gets the return value of B from that space.

在任何程序中，调用堆栈是内存中用于跟踪函数调用的空间。该内存中的空间用于存储函数的参数以及该函数的返回值。每当某个函数 A 调用另一个函数 B 时，A 从该空间获取 B 的返回值。

A recursive function is nothing special, it's just an ordinary function calling another function (that happens to be itself). So really, when a recursive function F calls itself, it's calling another function: F calls F', which calls F'', which calls F''', etc. It's just that F, F'', F''' etc. execute the same code, just with different inputs.

递归函数没什么特别的，它只是一个调用另一个函数（恰好是它自己）的普通函数。所以实际上，当递归函数 F 调用自身时，它正在调用另一个函数：F 调用 F'，它调用 F''，它调用 F''' 等等。只是 F、F''、F''' 等等. 执行相同的代码，只是输入不同。

The expression if (x == 1)is there to check when this process should be stopped. The return value of F''' is used by F''. The return value of F'' is used by F'. The return value of F' is used by F.

该表达式if (x == 1)用于检查何时应停止此进程。F''' 的返回值由 F'' 使用。F'' 的返回值由 F' 使用。F' 的返回值被 F 使用。

In Factorial of some number, the operation is (n) * (n-1) * (n-2) * .... * (1). I've highlighted the 1; this is the condition that's being checked.

在某个数的阶乘中，运算是 (n) * (n-1) * (n-2) * .... * ( 1)。我已经强调了 1; 这是正在检查的条件。

回答by David Xu

A recursive function breaks a big problem down into smaller cases.

递归函数将大问题分解为小问题。

Going over your program:

回顾你的程序：

call factorialfinder with 5, result is stored as 5 * factorialfinder(4)

call factorialfinder with 4, result is stored as 5 * 4 * factorialfinder(3)

call factorialfinder with 3, result is stored as 5 * 4 * 3 * factorialfinder(2)

call factorialfinder with 2, result is stored as 5 * 4 * 3 * 2 * factorialfinder(1)

call factorialfinder with 1, result is stored as 5 * 4 * 3 * 2 * 1

in essence it combines the result of a stack of calls to factorialfinder until you hit your base case, in this case x = 1.

本质上，它结合了对 factorialfinder 的一系列调用的结果，直到您达到基本情况，在这种情况下 x = 1。

回答by Servio

Well, the factorial function can be written using recursion or not, but the main consideration in the recursion is that this one uses the system stack, so, each call to the function is a item in the system stack, like this (read from the bottom to the top):

好吧，阶乘函数可以用递归写也可以，但是递归的主要考虑是这个函数使用了系统堆栈，所以，每次调用函数都是系统堆栈中的一个项目，像这样（从从下到上）：

Other consideration in the recursion function is that this one has two main code piece:

递归函数中的其他考虑因素是该函数有两个主要代码段：

1. The base case
2. The recursion case

1. 基本情况
2. 递归案例

In the base case, the recursive function returns the element that bounds the algorithm, and that stop the recursion. In the factorial this element is 1, because mathematically the factorial of number one is 1 by definition. For other numbers you don't know the factorial, because of that, you have to compute by using the formula, and one implementation of it is using recursion, so the recursive case.

在基本情况下，递归函数返回限制算法并停止递归的元素。在阶乘中，该元素为 1，因为在数学上，数字 1 的阶乘定义为 1。对于其他数字，您不知道阶乘，因此，您必须使用公式进行计算，并且它的一种实现是使用递归，因此是递归情况。

Example: The factorial of 5, the procedure is: 5*4*3*2*1 = 120, note you have to multiply each number from the top value until number 1, in other words, until the base case takes place which is the case that you already knew.

示例：5 的阶乘，过程为：5*4*3*2*1 = 120，注意你必须将每个数字从最高值乘到数字 1，换句话说，直到出现基本情况，即你已经知道的情况。

回答by Servio

#include<iostream>
using namespace std;

int factorial(int n);

int main()
{
    int n;

    cout << "Enter a positive integer: ";
    cin >> n;

    cout << "Factorial of " << n << " = " << factorial(n);

    return 0;
}

int factorial(int n)
{
    if(n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}