Python递归函数-这是怎么回事？

Question

我有一个简单的用python编写的阶乘函数，其中嵌入了一堆调试程序，以帮助我了解所发生的情况。但是，输出让我更加困惑。谁能帮我理解？ （顺便说一句，如果出现打印输出时序问题，我将其运行了几次，但得到的输出完全相同。）

recursive_function.py

def recursive(n):
  if n == 1:
    return 1
  print ('n : {}'.format(n))
  print ('recursive return value is: {}'.format(n*recursive(n-1)))
  return n*recursive(n-1)

x = recursive(5)
print('***** End result is: {}'.format(x))

-

(with line numbers)
1   n : 5
2   n : 4
3   n : 3
4   n : 2
5   recursive return value is: 2
6   recursive return value is: 6
7   n : 2
8   recursive return value is: 2
9   recursive return value is: 24
10  n : 3
11  n : 2
12  recursive return value is: 2
13  recursive return value is: 6
14  n : 2
15  recursive return value is: 2
16  recursive return value is: 120
17  n : 4
18  n : 3
19  n : 2
20  recursive return value is: 2
21  recursive return value is: 6
22  n : 2
23  recursive return value is: 2
24  recursive return value is: 24
25  n : 3
26  n : 2
27  recursive return value is: 2
28  recursive return value is: 6
29  n : 2
30  recursive return value is: 2
31  ***** End result is: 120

(cleaner output without line numbers)
n : 5
n : 4
n : 3
n : 2
recursive return value is: 2
recursive return value is: 6
n : 2
recursive return value is: 2
recursive return value is: 24
n : 3
n : 2
recursive return value is: 2
recursive return value is: 6
n : 2
recursive return value is: 2
recursive return value is: 120
n : 4
n : 3
n : 2
recursive return value is: 2
recursive return value is: 6
n : 2
recursive return value is: 2
recursive return value is: 24
n : 3
n : 2
recursive return value is: 2
recursive return value is: 6
n : 2
recursive return value is: 2
***** End result is: 120

Answer 1

该函数接受一个数字并计算factorial结果。

因此，对于5的值，结果是5 * 4 * 3 * 2，即120。

使该函数成为递归函数是有意义的，因为5的阶乘是4阶乘的5倍，4阶乘是3阶乘的4倍，依此类推。如果使用n = 1调用该函数，则阶乘将简单返回为1，并且可以停止递归。

认为这是在此处运行的实际算法：

1. 5的阶乘= 5 * 4的阶乘
2. 4的阶乘= 4 * 3的阶乘
3. 3的阶乘= 3 * 2的阶乘
4. 2的阶乘= 2 * 1的阶乘
5. 1的阶乘= 1

Answer 2

一个可能有用的版本：

def recursive(n):
  if n == 1:
    return 1
  print ('n : {}'.format(n))
  res = recursive(n-1)
  print ('return value is: {} (n={} * recursive({})={})'.format(n*res, n, n-1, res))
  return n*recursive(n-1)

x = recursive(5)
print('***** End result is: {}'.format(x))

更改：

• 不两次执行递归调用
• 在打印中添加了更多调试输出

输出：

n : 5
n : 4
n : 3
n : 2
return value is: 2 (n=2 * recursive(1)=1)
return value is: 6 (n=3 * recursive(2)=2)
return value is: 24 (n=4 * recursive(3)=6)
return value is: 120 (n=5 * recursive(4)=24)
***** End result is: 120

Answer 3

以下是查找整数的阶乘的递归函数的示例。

def calc_factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return (x * calc_factorial(x-1))

num = 4
print("The factorial of", num, "is", calc_factorial(num))

上面的例子，calc_factorial()是一个递归函数，它调用了它自己。

[当我们使用正整数调用此函数时，它将通过减少数量来递归调用自身。

每个函数调用数字与数字1的阶乘相乘，直到数字等于1。可以在以下步骤中说明此递归调用。

calc_factorial(4)              # 1st call with 4
4 * calc_factorial(3)          # 2nd call with 3
4 * 3 * calc_factorial(2)      # 3rd call with 2
4 * 3 * 2 * calc_factorial(1)  # 4th call with 1
4 * 3 * 2 * 1                  # return from 4th call as number=1
4 * 3 * 2                      # return from 3rd call
4 * 6                          # return from 2nd call
24                             # return from 1st call

当数字减少到1时，我们的递归操作结束。这称为基本条件。

每个递归函数必须具有停止递归的基本条件，否则该函数将无限地调用自身。

另一个例子

递归函数通常具有两个组成部分：

• 基本情况是确定何时应停止递归函数的条件
• 对自身的呼唤这是一个演示这两个组件的示例：

# Assume that remaining is a positive integer

    def hi_recursive(remaining):
        # The base case
        if remaining == 0:
            return
        print('hi')

        # Call to function, with a reduced remaining count
        hi_recursive(remaining - 1)

对于我们来说，

基本情况是如果剩余变量等于0，即我们必须打印多少剩余的“ hi”字符串。该函数仅返回。

在打印语句之后，我们再次调用hi_recursive，但剩余值减少了。这个很重要！如果不减少剩余值，则该函数将无限期运行。通常，当递归函数调用自身时，参数将更改为更接近基本情况。

让我们想象一下当我们call hi_recursive(3)：

时它是如何工作的。

函数打印'hi'之后，它以较低的值调用自身，直到达到0。为零时，函数返回到在[[hi_recursive(1)中被调用的位置，然后返回到在hi_recursive(2)中被调用的位置，最后返回到在hi_recursive(3)]中被调用的位置。 。