使用 Python 的递归问题 3
Issues with Recursion using Python 3
我的问题是递归工作时 python 在做什么。我明白了这个概念，但似乎循环中显式的内容在递归算法中是隐式的。我已经看到递归将循环遍历然后退回以获取答案的示例。我不明白。好像我没有写的代码正在发生。
我无法帮助 'seeing' return 声明 return 方程而不是 建立 方程和 return正在寻找答案。
有一些递归的例子很有意义，但斐波那契和阶乘类型的算法令人困惑。 （免责声明：我不想学习斐波那契或阶乘 ^_^。）
def main():
num = int(input("Please enter a non-negative integer.\n"))
fact = factorial(num)
print("The factorial of",num,"is",fact)
def factorial(num):
if num == 0:
return 1
else:
return num * factorial(num - 1)
main()
如果我们这样做 !10 我不禁认为它应该 return 每个方程的结果并对其进行循环。我不确定 python 在内存中是如何工作的。或者它如何知道它需要 return 10*9*8*7*6 的值...等等
而不是 returning
return 10 * (10 - 1)
return 9 * (9 - 1)
return 8 * (8 - 1)
我知道 return 调用函数所以它不能 return 任何东西......但是它如何处理它已经找到的值而不覆盖变量并丢失它的位置？
它是在盯着我看，还是有什么我不知道的？
把它想象成一道数学题。如果你知道!9的答案，你会如何计算!10？您只需将 !9 的值乘以 10。
这正是递归函数所做的；它只是将 num 的阶乘表示为 num 乘以 num - 1 的阶乘。唯一不起作用的数字是 0，但 0 的阶乘是已知的，它是 1.
所以，10 的阶乘基本上是：
10 * factorial(9) ==10 * 9 * factorial(8) ==10 * 9 * 8 * factorial(7) ==10 * 9 * 8 * 7 * factorial(6) ==10 * 9 * 8 * 7 * 6 * factorial(5) ==10 * 9 * 8 * 7 * 6 * 5 * factorial(4) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * factorial(3) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * factorial(2) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * factorial(1) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * factorial(0) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1
请注意，每个 factorial() 调用都会得到一组 新变量 。不会发生覆盖；这是对该功能的全新调用。每次调用中 num 的值完全独立于对该函数的所有其他调用。
如果有帮助，请尝试使用笔记本跟踪功能信息。在页面上写下变量，在手动执行代码时更新它们。对于每个新函数调用，翻页并从下一张纸开始，在其中写下变量。你会在第一页写 10，然后在第二页写 9 (num - 1)，等等。返回意味着取 returned 值，从笔记本中取出页面 并返回笔记本中的页面，用那个 return 值更新那里的变量。
Python 做完全相同的事情，使用 frame 对象来跟踪变量。每个函数调用都是一个新的帧，当一个函数returns时，帧会再次被丢弃。该调用的所有变量都随框架消失了。
另外，Python 不关心 你在这里重复使用相同的函数。您可以创建 11 个单独的函数，每个函数都有一个单独的名称和一个单独的 num 名称：
def factorial10(num10):
if num10 == 0:
return 1
else:
return num10 * factorial9(num10 - 1)
def factorial9(num9):
if num9 == 0:
return 1
else:
return num9 * factorial8(num9 - 1)
def factorial8(num8):
if num8 == 0:
return 1
else:
return num8 * factorial7(num8 - 1)
# ...
# etc. all the way to
def factorial0(num0):
if num0 == 0:
return 1
else:
return num0 * factorialminus1(num0 - 1)
和 Python 看不出这些函数与原始函数有任何区别。将执行完全相同的工作，但不是重复使用相同的函数，而是使用具有 相同行为 的不同函数对象。只是名字变了。
因此，递归只是将一系列函数调用链接在一起的巧妙方法。这些函数调用都是独立的，它们不关心其他函数的局部变量在做什么。 Python 不需要 'know' 任何东西，它只需要为你执行函数，当它遇到另一个函数调用时，执行那个函数调用并使用 return 值。该函数是相同的函数还是不同的函数没有任何区别。
这是一个很难以完全权威的方式回答的问题 -- 我认为不同的人对递归有不同的思考方式。 我思考递归的方式是强迫自己以一种非常有纪律的、抽象的方式思考函数是什么。函数只是一个映射。这在原则上很简单，但在实践中很容易忘记，尤其是如果您习惯于以命令式的方式思考——也就是说，将程序视为指令集。
暂时忘掉指令，考虑最抽象形式的阶乘函数：
X Y
--------------------
0 ------> 1
1 ------> 1
2 ------> 2
3 ------> 6
4 ------> 24
5 ------> 120
6 ------> 720
...
暂时不用担心如何计算。想想抽象映射。现在让我们考虑如何制作这个函数的递归版本。我们需要什么？那么，我们需要一个函数来创建不同的映射——不是从 [1, 2, 3, ...] 到阶乘的映射，而是从 Y 的一个值到下一个值的映射。换句话说（现在使用小写）：
x y
--------------------
1 ------> 1
1 ------> 2
2 ------> 6
6 ------> 24
24 ------> 120
120 ------> 720
720 ------> 5040
...
现在我们来考虑如何计算this。立即出现一个问题：1 第一次映射到 1，第二次映射到 2。所以我们知道我们将不得不编写一个特例来区分这两者。但是对于其他人来说，这很简单，对吧？只需将 x 乘以它在列表中的位置即可。所以这意味着对于映射的所有这些部分，我们只需要知道两件事：x，以及它在列表中的 position：
def factorial_recurrence(x, position):
return x * position
请注意，此函数现在有两个参数，因此它实际上与上面的函数略有不同：
x, p y
------------------------
1 0 ------> 1
1 1 ------> 2
2 2 ------> 6
6 3 ------> 24
24 4 ------> 120
120 5 ------> 720
720 6 ------> 5040
这非常清楚地显示了我们如何区分来自 1 的两个映射。现在我们只需要想出一种获取位置信息的方法即可。恰好 position 与 X 的值相同。因此，一种简单的方法是使用循环。在这里，我们通过简单地将 x 设置为 1 并在 1 而不是 0:
开始循环来处理 X == 0
def factorial(X):
x = 1
for position in range(1, X + 1):
x = factorial_recurrence(x, position)
return x
现在注意x的值被传递给factorial_recurrence，然后结果被保存为x。
所以这里真正发生的是函数的输出被传递回函数。这是重大发现：
这就是递归！
这在关键意义上已经是递归算法了。只是这里的表示是inside-out，而且函数还合并了递归过程之外的position信息。要明白我的意思，请看这个：
def even_factorial(X):
x = 1
for position in range(2, X + 1, 2):
x = factorial_recurrence(factorial_recurrence(x, position - 1), position)
return x
对于 X 的每个偶数值，这给出与 factorial 相同的结果。 （对于 X 的奇数，它给出了 X - 1 的结果。）而且我们不必停在那里。我们可以对 X 的每三个值做同样的事情（为清楚起见打破嵌套）：
def third_factorial(X):
x = 1
for position in range(3, X + 1, 3):
x = factorial_recurrence(
factorial_recurrence(
factorial_recurrence(
x,
position - 2
),
position - 1
),
position
)
return x
现在每 4 次、每 5 次等做同样的事情。如果你继续这个过程，那么对于任何给定的 X，你最终会创建一个函数，它将 return 只有 1 直到你通过 X，然后当你通过 X，你将得到 X 的阶乘。
在这一点上，递归的技巧只是认识到我们可以通过让 factorial 调用自身来自动完成将循环内部翻转的过程。每次调用 factorial 时，它只是在最后一个调用中嵌套另一个 factorial_recurrence 调用——除非 X 为 0，在这种情况下，它 returns 1 , 终止嵌套调用序列。
def factorial(X):
if X == 0:
return 1
else:
return factorial_recurrence(factorial(X - 1), X)
所以这是一种复杂的递归思考方式，但它的价值在于它非常清楚地显示了递归函数的抽象与其在命令式代码中的具体实现之间的关系。
我的问题是递归工作时 python 在做什么。我明白了这个概念，但似乎循环中显式的内容在递归算法中是隐式的。我已经看到递归将循环遍历然后退回以获取答案的示例。我不明白。好像我没有写的代码正在发生。
我无法帮助 'seeing' return 声明 return 方程而不是 建立 方程和 return正在寻找答案。
有一些递归的例子很有意义，但斐波那契和阶乘类型的算法令人困惑。 （免责声明：我不想学习斐波那契或阶乘 ^_^。）
def main():
num = int(input("Please enter a non-negative integer.\n"))
fact = factorial(num)
print("The factorial of",num,"is",fact)
def factorial(num):
if num == 0:
return 1
else:
return num * factorial(num - 1)
main()
如果我们这样做 !10 我不禁认为它应该 return 每个方程的结果并对其进行循环。我不确定 python 在内存中是如何工作的。或者它如何知道它需要 return 10*9*8*7*6 的值...等等
而不是 returning return 10 * (10 - 1) return 9 * (9 - 1) return 8 * (8 - 1)
我知道 return 调用函数所以它不能 return 任何东西......但是它如何处理它已经找到的值而不覆盖变量并丢失它的位置？
它是在盯着我看，还是有什么我不知道的？
把它想象成一道数学题。如果你知道!9的答案，你会如何计算!10？您只需将 !9 的值乘以 10。
这正是递归函数所做的；它只是将 num 的阶乘表示为 num 乘以 num - 1 的阶乘。唯一不起作用的数字是 0，但 0 的阶乘是已知的，它是 1.
所以，10 的阶乘基本上是：
10 * factorial(9) ==10 * 9 * factorial(8) ==10 * 9 * 8 * factorial(7) ==10 * 9 * 8 * 7 * factorial(6) ==10 * 9 * 8 * 7 * 6 * factorial(5) ==10 * 9 * 8 * 7 * 6 * 5 * factorial(4) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * factorial(3) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * factorial(2) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * factorial(1) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * factorial(0) ==10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1
请注意，每个 factorial() 调用都会得到一组 新变量 。不会发生覆盖；这是对该功能的全新调用。每次调用中 num 的值完全独立于对该函数的所有其他调用。
如果有帮助，请尝试使用笔记本跟踪功能信息。在页面上写下变量，在手动执行代码时更新它们。对于每个新函数调用，翻页并从下一张纸开始，在其中写下变量。你会在第一页写 10，然后在第二页写 9 (num - 1)，等等。返回意味着取 returned 值，从笔记本中取出页面 并返回笔记本中的页面，用那个 return 值更新那里的变量。
Python 做完全相同的事情，使用 frame 对象来跟踪变量。每个函数调用都是一个新的帧，当一个函数returns时，帧会再次被丢弃。该调用的所有变量都随框架消失了。
另外，Python 不关心 你在这里重复使用相同的函数。您可以创建 11 个单独的函数，每个函数都有一个单独的名称和一个单独的 num 名称：
def factorial10(num10):
if num10 == 0:
return 1
else:
return num10 * factorial9(num10 - 1)
def factorial9(num9):
if num9 == 0:
return 1
else:
return num9 * factorial8(num9 - 1)
def factorial8(num8):
if num8 == 0:
return 1
else:
return num8 * factorial7(num8 - 1)
# ...
# etc. all the way to
def factorial0(num0):
if num0 == 0:
return 1
else:
return num0 * factorialminus1(num0 - 1)
和 Python 看不出这些函数与原始函数有任何区别。将执行完全相同的工作，但不是重复使用相同的函数，而是使用具有 相同行为 的不同函数对象。只是名字变了。
因此，递归只是将一系列函数调用链接在一起的巧妙方法。这些函数调用都是独立的，它们不关心其他函数的局部变量在做什么。 Python 不需要 'know' 任何东西，它只需要为你执行函数，当它遇到另一个函数调用时，执行那个函数调用并使用 return 值。该函数是相同的函数还是不同的函数没有任何区别。
这是一个很难以完全权威的方式回答的问题 -- 我认为不同的人对递归有不同的思考方式。 我思考递归的方式是强迫自己以一种非常有纪律的、抽象的方式思考函数是什么。函数只是一个映射。这在原则上很简单，但在实践中很容易忘记，尤其是如果您习惯于以命令式的方式思考——也就是说，将程序视为指令集。
暂时忘掉指令，考虑最抽象形式的阶乘函数：
X Y
--------------------
0 ------> 1
1 ------> 1
2 ------> 2
3 ------> 6
4 ------> 24
5 ------> 120
6 ------> 720
...
暂时不用担心如何计算。想想抽象映射。现在让我们考虑如何制作这个函数的递归版本。我们需要什么？那么，我们需要一个函数来创建不同的映射——不是从 [1, 2, 3, ...] 到阶乘的映射，而是从 Y 的一个值到下一个值的映射。换句话说（现在使用小写）：
x y
--------------------
1 ------> 1
1 ------> 2
2 ------> 6
6 ------> 24
24 ------> 120
120 ------> 720
720 ------> 5040
...
现在我们来考虑如何计算this。立即出现一个问题：1 第一次映射到 1，第二次映射到 2。所以我们知道我们将不得不编写一个特例来区分这两者。但是对于其他人来说，这很简单，对吧？只需将 x 乘以它在列表中的位置即可。所以这意味着对于映射的所有这些部分，我们只需要知道两件事：x，以及它在列表中的 position：
def factorial_recurrence(x, position):
return x * position
请注意，此函数现在有两个参数，因此它实际上与上面的函数略有不同：
x, p y
------------------------
1 0 ------> 1
1 1 ------> 2
2 2 ------> 6
6 3 ------> 24
24 4 ------> 120
120 5 ------> 720
720 6 ------> 5040
这非常清楚地显示了我们如何区分来自 1 的两个映射。现在我们只需要想出一种获取位置信息的方法即可。恰好 position 与 X 的值相同。因此，一种简单的方法是使用循环。在这里，我们通过简单地将 x 设置为 1 并在 1 而不是 0:
X == 0
def factorial(X):
x = 1
for position in range(1, X + 1):
x = factorial_recurrence(x, position)
return x
现在注意x的值被传递给factorial_recurrence，然后结果被保存为x。
所以这里真正发生的是函数的输出被传递回函数。这是重大发现：
这就是递归！
这在关键意义上已经是递归算法了。只是这里的表示是inside-out，而且函数还合并了递归过程之外的position信息。要明白我的意思，请看这个：
def even_factorial(X):
x = 1
for position in range(2, X + 1, 2):
x = factorial_recurrence(factorial_recurrence(x, position - 1), position)
return x
对于 X 的每个偶数值，这给出与 factorial 相同的结果。 （对于 X 的奇数，它给出了 X - 1 的结果。）而且我们不必停在那里。我们可以对 X 的每三个值做同样的事情（为清楚起见打破嵌套）：
def third_factorial(X):
x = 1
for position in range(3, X + 1, 3):
x = factorial_recurrence(
factorial_recurrence(
factorial_recurrence(
x,
position - 2
),
position - 1
),
position
)
return x
现在每 4 次、每 5 次等做同样的事情。如果你继续这个过程，那么对于任何给定的 X，你最终会创建一个函数，它将 return 只有 1 直到你通过 X，然后当你通过 X，你将得到 X 的阶乘。
在这一点上，递归的技巧只是认识到我们可以通过让 factorial 调用自身来自动完成将循环内部翻转的过程。每次调用 factorial 时，它只是在最后一个调用中嵌套另一个 factorial_recurrence 调用——除非 X 为 0，在这种情况下，它 returns 1 , 终止嵌套调用序列。
def factorial(X):
if X == 0:
return 1
else:
return factorial_recurrence(factorial(X - 1), X)
所以这是一种复杂的递归思考方式，但它的价值在于它非常清楚地显示了递归函数的抽象与其在命令式代码中的具体实现之间的关系。