474 lines
16 KiB
Plaintext
474 lines
16 KiB
Plaintext
{
|
||
"cells": [
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# 递归函数"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## 递归（Recursion）"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"在函数中有个理解门槛比较高的概念：**递归函数**（Recursive Functions）—— 那些**在自身内部调用自身的函数**。说起来都比较拗口。"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"在所有的项目中，都是非常常用的，这样子写，虽然运算复杂了、逻辑性要求更高，但是那是计算机考虑的事情，对人而言，写的代码少了，预计的结果出来了！"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"先看一个例子，我们想要有个能够计算 `n` 的*阶乘*（factorial）`n!` 的函数，`f()`，规则如下：\n",
|
||
"\n",
|
||
"> - `n! = n × (n-1) × (n-2)... × 1`\n",
|
||
"> - 即，`n! = n × (n-1)!`\n",
|
||
"> - 且，`n >= 1`\n",
|
||
">\n",
|
||
"> **注意**：以上是数学表达，不是程序，所以，`=` 在这一小段中是 “*等于*” 的意思，**不是程序语言中的赋值符号**。\n",
|
||
"\n",
|
||
"于是，计算 `f(n)` 的 Python 程序如下：\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 1,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"120\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def f(n):\n",
|
||
" if n == 1:\n",
|
||
" return 1\n",
|
||
" else:\n",
|
||
" return n * f(n-1)\n",
|
||
" \n",
|
||
"print(f(5))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## 递归函数的执行过程"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"以 factorial(5) 为例，让我们看看程序的流程：\n",
|
||
"\n",
|
||
"\n",
|
||
"\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"当 f(5) 被调用之后，函数开始运行……\n",
|
||
"* 因为 `5 > 1`，所以，在计算 `n * f(n-1)` 的时候要再次调用自己 `f(4)`；所以必须等待 `f(4)` 的值返回；\n",
|
||
"* 因为 `4 > 1`，所以，在计算 `n * f(n-1)` 的时候要再次调用自己 `f(3)`；所以必须等待 `f(3)` 的值返回；\n",
|
||
"* 因为 `3 > 1`，所以，在计算 `n * f(n-1)` 的时候要再次调用自己 `f(2)`；所以必须等待 `f(2)` 的值返回；\n",
|
||
"* 因为 `2 > 1`，所以，在计算 `n * f(n-1)` 的时候要再次调用自己 `f(1)`；所以必须等待 `f(1)` 的值返回；\n",
|
||
"* 因为 `1 == 1`，所以，这时候不会再次调用 `f()` 了，于是递归结束，开始返回，这次返回的是 `1`；\n",
|
||
"* 下一步返回的是 `2 * 1`；\n",
|
||
"* 下一步返回的是 `3 * 2`；\n",
|
||
"* 下一步返回的是 `4 * 6`；\n",
|
||
"* 下一步返回的是 `5 * 24` —— 至此，外部调用 `f(5)` 的最终返回值是 `120`……\n",
|
||
"\n",
|
||
"加上一些输出语句之后，能更清楚地看到大概的执行流程："
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 1,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Call f(5)...\n",
|
||
"\tn = 5\n",
|
||
"\tn = 4\n",
|
||
"\tn = 3\n",
|
||
"\tn = 2\n",
|
||
"\tn = 1\n",
|
||
"Returning...\n",
|
||
"\tn = 1 return: 1\n",
|
||
"\tn = 2 return: 2\n",
|
||
"\tn = 3 return: 6\n",
|
||
"\tn = 4 return: 24\n",
|
||
"\tn = 5 return: 120\n",
|
||
"Get out of f(n), and f(5) = 120\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def f(n):\n",
|
||
" print('\\tn =', n)\n",
|
||
" if n == 1:\n",
|
||
" print('Returning...')\n",
|
||
" print('\\tn =', n, 'return:', 1)\n",
|
||
" return 1\n",
|
||
" else:\n",
|
||
" r = n * f(n-1)\n",
|
||
" print('\\tn =', n, 'return:', r)\n",
|
||
" return r\n",
|
||
" \n",
|
||
"print('Call f(5)...')\n",
|
||
"print('Get out of f(n), and f(5) =', f(5))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## 递归的终点"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"递归函数在内部必须有一个能够让自己停止调用自己的方式，否则永远循环下去了……\n",
|
||
"\n",
|
||
"其实，我们所有人很小就见过递归应用，只不过，那时候不知道那就是递归而已。听过那个无聊的故事罢？\n",
|
||
"\n",
|
||
"> 山上有座庙，庙里有个和尚，和尚讲故事，说……\n",
|
||
"> > 山上有座庙，庙里有个和尚，和尚讲故事，说……\n",
|
||
"> > > 山上有座庙，庙里有个和尚，和尚讲故事，说……\n",
|
||
"\n",
|
||
"写成 Python 程序大概是这样：\n",
|
||
"\n",
|
||
"```python\n",
|
||
"def a_monk_telling_story():\n",
|
||
" print('山上有座庙，庙里有个和尚，和尚讲故事，他说…… ')\n",
|
||
" return a_monk_telling_story()\n",
|
||
"\n",
|
||
"a_monk_telling_story()\n",
|
||
"```\n",
|
||
"\n",
|
||
"这是个*无限循环*的递归，因为这个函数里*没有设置中止自我调用的条件*。无限循环还有个不好听的名字，叫做 “死循环”。"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"在著名的电影**盗梦空间**（_2010_）里，从整体结构上来看，“入梦” 也是个 “递归函数”。只不过，这个函数和 `a_monk_telling_story()` 不一样，它并不是死循环 —— 因为它设定了*中止自我调用的条件*：\n",
|
||
"\n",
|
||
"> 在电影里，醒过来的条件有两个\n",
|
||
">> * 一个是在梦里死掉；\n",
|
||
">> * 一个是在梦里被 kicked 到……\n",
|
||
">\n",
|
||
"> 如果这两个条件一直不被满足，那就进入 limbo 状态 —— 其实就跟死循环一样，出不来了……\n",
|
||
"\n",
|
||
"为了演示，我把故事情节改变成这样：\n",
|
||
"> * 入梦，`in_dream()`，是个递归函数；\n",
|
||
"> * 入梦之后醒过来的条件有两个：\n",
|
||
">> * 一个是在梦里死掉，`dead is True`；\n",
|
||
">> * 一个是在梦里被 kicked，`kicked is True`……\n",
|
||
">>\n",
|
||
">> 以上两个条件中任意一个被满足，就苏醒……\n",
|
||
"\n",
|
||
"至于为什么会死掉，如何被 kick，我偷懒了一下：管它怎样，管它如何，反正，每个条件被满足的概率是 1/10……（也只有这样，我才能写出一个简短的，能够运行的 “*盗梦空间程序*”。）\n",
|
||
"\n",
|
||
"把这个很抽象的故事写成 Python 程序，看看一次入梦之后能睡多少天，大概是这样："
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 9,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"dead: False kicked: False\n",
|
||
"dead: False kicked: False\n",
|
||
"dead: False kicked: False\n",
|
||
"dead: True kicked: False\n",
|
||
"I slept 4 days, and was dead to wake up...\n",
|
||
"The in_dream() function returns: 4\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"import random\n",
|
||
"\n",
|
||
"def in_dream(day=0, dead=False, kicked=False):\n",
|
||
" dead = not random.randrange(0,10) # 1/10 probability to be dead\n",
|
||
" kicked = not random.randrange(0,10) # 1/10 probability to be kicked\n",
|
||
" day += 1\n",
|
||
" print('dead:', dead, 'kicked:', kicked)\n",
|
||
" \n",
|
||
" if dead:\n",
|
||
" print((f\"I slept {day} days, and was dead to wake up...\"))\n",
|
||
" return day\n",
|
||
" elif kicked:\n",
|
||
" print(f\"I slept {day} days, and was kicked to wake up...\")\n",
|
||
" return day\n",
|
||
" \n",
|
||
" return in_dream(day)\n",
|
||
" \n",
|
||
"print('The in_dream() function returns:', in_dream())"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 10,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"ename": "RecursionError",
|
||
"evalue": "maximum recursion depth exceeded",
|
||
"output_type": "error",
|
||
"traceback": [
|
||
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
|
||
"\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)",
|
||
"Cell \u001b[0;32mIn[10], line 3\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mx\u001b[39m(n):\n\u001b[1;32m 2\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m n \u001b[38;5;241m*\u001b[39m x(n\u001b[38;5;241m-\u001b[39m\u001b[38;5;241m1\u001b[39m)\n\u001b[0;32m----> 3\u001b[0m \u001b[43mx\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m5\u001b[39;49m\u001b[43m)\u001b[49m\n",
|
||
"Cell \u001b[0;32mIn[10], line 2\u001b[0m, in \u001b[0;36mx\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mx\u001b[39m(n):\n\u001b[0;32m----> 2\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m n \u001b[38;5;241m*\u001b[39m \u001b[43mx\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\n",
|
||
"Cell \u001b[0;32mIn[10], line 2\u001b[0m, in \u001b[0;36mx\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mx\u001b[39m(n):\n\u001b[0;32m----> 2\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m n \u001b[38;5;241m*\u001b[39m \u001b[43mx\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\n",
|
||
" \u001b[0;31m[... skipping similar frames: x at line 2 (2969 times)]\u001b[0m\n",
|
||
"Cell \u001b[0;32mIn[10], line 2\u001b[0m, in \u001b[0;36mx\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mx\u001b[39m(n):\n\u001b[0;32m----> 2\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m n \u001b[38;5;241m*\u001b[39m \u001b[43mx\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\n",
|
||
"\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def x(n):\n",
|
||
" return n * x(n-1)\n",
|
||
"x(5)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"不用深究上面盗梦空间这个程序的其它细节，不过，通过以上三个递归程序 —— 两个很扯淡的例子，一个正经例子 —— 你已经看到了递归函数的共同特征：\n",
|
||
"\n",
|
||
"> 1. 在 `return` 语句中返回的是*自身的调用*（或者是*含有自身的表达式*）\n",
|
||
"> 2. 为了避免死循环，*一定要有至少一个条件*下返回的不再是自身调用……"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## 变量的作用域"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"再回来看计算阶乘的程序 —— 这是正经程序。这次我们把程序名写完整，`factorial()`:"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 6,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"120\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def factorial(n):\n",
|
||
" if n == 1:\n",
|
||
" return 1\n",
|
||
" else:\n",
|
||
" return n * factorial(n-1)\n",
|
||
" \n",
|
||
"print(factorial(5))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"最初的时候，这个函数的执行流程之所以令人迷惑，是因为初学者对*变量*的**作用域**把握得不够充分。\n",
|
||
"\n",
|
||
"变量根据作用域，可以分为两种：全局变量（Global Variables）和局部变量（Local Variables）。\n",
|
||
"\n",
|
||
"可以这样简化理解：\n",
|
||
"\n",
|
||
"> * 在函数内部被赋值而后使用的，都是*局部变量*，它们的作用域是*局部*，无法被函数外的代码调用；\n",
|
||
"> * 在所有函数之外被赋值而后开始使用的，是*全局变量*，它们的作用域是*全局*，在函数内外都可以被调用。\n",
|
||
"\n",
|
||
"定义如此，但通常程序员们会严格地遵守一条原则：\n",
|
||
"\n",
|
||
"> 在函数内部绝对不调用全局变量。即便是必须改变全局变量，也只能通过函数的返回值在函数外改变全局变量。\n",
|
||
"\n",
|
||
"你也必须遵守同样的原则。而这个原则同样可以在日常的工作生活中 “调用”：\n",
|
||
"\n",
|
||
"> 做事的原则：自己的事自己做，别人的事，最多通过自己的产出让他们自己去搞……"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"再仔细观察一下以下代码。当一个变量被当做参数传递给一个函数的时候，这个变量本身并不会被函数所改变。比如，`a = 5`，而后，再把 `a` 当作参数传递给 `f(a)` 的时候，这个函数当然应该返回它内部任务完成之后应该传递回来的值，但 `a` 本身不会被改变。"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 7,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"5 120\n",
|
||
"120 120\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def factorial(n):\n",
|
||
" if n == 1:\n",
|
||
" return 1\n",
|
||
" else:\n",
|
||
" return n * factorial(n-1)\n",
|
||
" \n",
|
||
"a = 5\n",
|
||
"b = factorial(a) # a 并不会因此改变；\n",
|
||
"print(a, b)\n",
|
||
"a = factorial(a) # 这是你主动为 a 再一次赋值……\n",
|
||
"print(a, b)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"理解了这一点之后，再看 `factorial()` 这个递归函数的递归执行过程，你就能明白这个事实：\n",
|
||
"\n",
|
||
"> 在每一次 factorial(n) 被调用的时候，它都会形成一个作用域，`n` 这个变量作为参数把它的值传递给了函数，*但是*，`n` 这个变量本身并不会被改变。\n",
|
||
"\n",
|
||
"我们再修改一下上面的代码："
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 8,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"5 120\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def factorial(n):\n",
|
||
" if n == 1:\n",
|
||
" return 1\n",
|
||
" else:\n",
|
||
" return n * factorial(n-1)\n",
|
||
" \n",
|
||
"n = 5 # 这一次，这个变量名称是 n\n",
|
||
"m = factorial(n) # n 并不会因此改变；\n",
|
||
"print(n, m)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"在 `m = factorial(n)` 这一句中，`n` 被 `factorial()` 当做参数调用了，但无论函数内部如何操作，并不会改变变量 `n` 的值。\n",
|
||
"\n",
|
||
"关键的地方在这里：在函数内部出现的变量 `n`，和函数外部的变量 `n` 不是一回事 —— **它们只是名称恰好相同而已**，函数参数定义的时候，用别的名称也没什么区别："
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 1,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"5 120\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"def factorial(x): # 在这个语句块中出现的变量，都是局部变量\n",
|
||
" if x == 1:\n",
|
||
" return 1\n",
|
||
" else:\n",
|
||
" return x * factorial(x-1)\n",
|
||
" \n",
|
||
"n = 5 # 这一次，这个变量名称是 n\n",
|
||
"m = factorial(n) # n 并不会因此改变；\n",
|
||
"print(n, m)\n",
|
||
"# 这个例子和之前再之前的示例代码有什么区别吗？\n",
|
||
"# 本质上没区别，就是变量名称换了而已……"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"函数开始执行的时候，`x` 的值，是由外部代码（即，函数被调用的那一句）传递进来的。即便函数内部的变量名称与外部的变量名称相同，它们也不是同一个变量。"
|
||
]
|
||
}
|
||
],
|
||
"metadata": {
|
||
"kernelspec": {
|
||
"display_name": "Python 3",
|
||
"language": "python",
|
||
"name": "python3"
|
||
},
|
||
"language_info": {
|
||
"codemirror_mode": {
|
||
"name": "ipython",
|
||
"version": 3
|
||
},
|
||
"file_extension": ".py",
|
||
"mimetype": "text/x-python",
|
||
"name": "python",
|
||
"nbconvert_exporter": "python",
|
||
"pygments_lexer": "ipython3",
|
||
"version": "3.8.2"
|
||
}
|
||
},
|
||
"nbformat": 4,
|
||
"nbformat_minor": 2
|
||
}
|