{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 4.6 递归"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<font size=\"6\">1.斐波那契数列前n项</font>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<font size=\"6\">0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,……</font>\n",
"<img src = \"images/ch4/4.gif\">\n",
"斐波那契数列又称黄金分割数列，这个数列从第3项开始，后一项的值总是与他前面两项的和的值相等。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"在数学上，以递推的方法定义："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```python\n",
"F(1)=0\n",
"F(2)=1 \n",
"F(n)=F(n - 1)+F(n - 2) (n ≥ 2，n ∈ N*)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"在数学上，也可以给出归纳方法定义："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```python\n",
"f(n) = 0 (n=0)\n",
"f(n) = 1 (n=1)\n",
"f(n) = f(n - 1) + f(n - 2) (n ≥ 2，n ∈ N*)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"很明显这是一个分段函数，可以用二分支来实现："
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdin",
"output_type": "stream",
"text": [
" 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"5\n"
]
}
],
"source": [
"def fibonacci(n):\n",
" \"\"\"定义递归函数，接收非负整数n，返回斐波那契数列的第n项\"\"\"\n",
" if n == 0: # 第一项为1\n",
" return 0\n",
" elif n == 1: # 第二项为1\n",
" return 1\n",
" else:\n",
" return fibonacci(n - 1) + fibonacci(n - 2) # 其他项等于前两项之和\n",
"\n",
"\n",
"num = int(input()) # 输入非负整数\n",
"print(fibonacci(num)) # 调用递归函数求斐波那契数列的第n项并输出"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"需要注意的是，在else分支下面，程序的返回值中再次调用了函数fibonacci()，只是参数值变小了。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"修改一下描述：\n",
"```python\n",
"f(n) = n (n≤1)\n",
"f(n) = f(n - 1) + f(n - 2) (n ≥ 2，n ∈ N*)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdin",
"output_type": "stream",
"text": [
" -7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"-7\n"
]
}
],
"source": [
"def fibonacci(n):\n",
" \"\"\"定义递归函数，接收非负整数n，返回斐波那契数列的第n项\"\"\"\n",
" if n <= 1: # 前两项为0或1\n",
" return n\n",
" else:\n",
" return fibonacci(n - 1) + fibonacci(n - 2) # 其他项等于前两项之和\n",
"\n",
"\n",
"num = int(input()) # 输入非负整数\n",
"print(fibonacci(num)) # 调用递归函数求斐波那契数列的第n项并输出"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"类似的问题还有："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"2.阶乘计算：递归也常用于计算阶乘。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def factorial(n):\n",
" if n == 1:\n",
" return 1\n",
" else:\n",
" return n * factorial(n-1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"3.汉诺塔问题：汉诺塔问题是一个经典的递归问题。"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"def hanoi(n, source, target, auxiliary):\n",
" if n > 0:\n",
" hanoi(n - 1, source, auxiliary, target)\n",
" print('Move disk from {} to {}'.format(source, target))\n",
" hanoi(n - 1, auxiliary, target, source)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"4.\"五人分鱼\"。问题描述如下：五个人在夜间捕到一堆鱼，约定第二天分鱼。第二天早上，第一个人醒来，将鱼分为五份，发现多了一条，就扔掉这条，拿走自己的一份。后来第二个、第三个、第四个、第五个人都是这样分鱼的。问他们至少捕到多少条鱼？"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def fish(n, total):\n",
" # n是还未分鱼的人数，total是当前的鱼数\n",
" if n == 0: # 所有的人都已经分过鱼了\n",
" return total # 返回最后的鱼数\n",
" elif total % 5 == 1: # 当前的鱼数可以被5整除，并且还剩一条鱼\n",
" # 递归调用fish函数，n减1，total更新为剩下的鱼数\n",
" return fish(n - 1, (total - 1) * 4 / 5)\n",
" else: # 当前的鱼数不能被5整除，或者不剩一条鱼\n",
" return False # 返回False，表示这个鱼数不符合条件\n",
"\n",
"total = 1 # 从1开始尝试\n",
"while True: # 不断尝试，直到找到一个符合条件的鱼数\n",
" if fish(5, total): # 如果这个鱼数符合条件\n",
" print(f\"五人至少合伙捕到{total}条鱼\") # 输出这个鱼数\n",
" break # 结束循环\n",
" total += 1 # 尝试下一个鱼数"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"5.有一座八层宝塔，每一层都有一些琉璃灯，每一层的灯数都是上一层的二倍，已知共有765盏琉璃灯，求解每层各有多少。"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 6, 12, 24, 48, 96, 192, 384]\n"
]
}
],
"source": [
"def lamps(n, total):\n",
" if n == 1: # 如果只有一层\n",
" return [total] # 返回总灯数\n",
" else:\n",
" # 第一层的灯数是总灯数除以(2^n - 1)\n",
" first = total // (2 ** n - 1)\n",
" # 返回第一层的灯数和剩下层的灯数\n",
" return [first] + lamps(n - 1, total - first)\n",
"\n",
"\n",
"print(lamps(8, 765)) # 输出每层的灯数\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"6.猴子吃桃问题：猴子摘下了n个桃子，第一天吃了一半又多吃了一个，第二天也是吃了剩下的一半又多吃了一个，到了第十天想再吃时，发现只剩下一个桃子了。问猴子第一天共摘了多少个桃子？"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def peaches(day):\n",
" if day == 10: # 第10天只剩下一个桃子\n",
" return 1\n",
" else:\n",
" # 第day天的桃子数是第day+1天的桃子数加一后的两倍\n",
" return (peaches(day + 1) + 1) * 2\n",
"\n",
"print(peaches(1)) # 输出第一天的桃子数"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<font color=Red>__递归（Recursion）__</font>是指在函数的定义中<font color=Red>__调用函数自身__</font>的方法。\n",
"\n",
"递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个，所以就产生了函数调用它自身的情况。当然这样的函数必须有明显的结束条件，<font color=Red>__以避免产生无限递归的问题__</font>。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"函数内部可以调用其他函数。如果一个函数内部<font color=Red>__调用函数本身__</font>，这个函数就是<font color=Red>__递归函数__</font>。\n",
"\n",
"递归的解题思路十分擅长解决除了规模大小不同，其他完全一样的问题。比如阶乘，Fibonacci数列等问题，用递归方法来解决，可以用较少的代码来完成。 "
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"def fact(n):\n",
" '''定义递归函数，接收非负整数n，返回n的阶乘'''\n",
" if n == 0: # 必须有一个终止条件\n",
" return 1 # 此时返回值确定值\n",
" else:\n",
" return n * fact(n - 1) # 调用fact()自身，即当前数n的阶乘等于n与前一个数n-1的阶乘之积\n",
"\n",
"num = int(input()) #输入非负整数\n",
"print(fact(num)) #调用递归函数求阶乘并输出"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"函数fact(5)开始调用时，传入参数为5，返回值为5 * fact(4)，即调用fact()函数自身，传入值为4，返回值为4 * fact(3)....，以此类推，函数每调用一次，问题的<font color=Red>__规模减小1__</font>，直至遇到函数的<font color=Red>__结束条件__</font>n == 0，终止函数的调用，再<font color=Red>__逐层返回__</font>，逆向运算得到结果。\n",
"\n",
"下图说明了递归求解的过程："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src=\"images/ch4/5.png\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<font color=Red>__递归函数必须满足如下特性：__</font>\n",
"1. 必须有一个明确的递归终止条件。\n",
"递归在有限次调用后要进行回溯才能得到最终的结果，那么必然应该有一个明确的临界点，程序一旦到达了这个临界点，就不用继续函数的调用而开始回溯，该临界点可以防止无限递归。\n",
"2. 给出递归终止时的处理办法。\n",
"在递归的临界点应该直接给出问题的解决方案。\n",
"3. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少或更接近于解。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<font color=Red>__能用递归解决的问题__</font>必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。从程序实现的角度而言，需要抽象出一个简单的重复的逻辑，以便使用相同的方式解决子问题。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<font color=Red>__递归函数的优点__</font>是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。<font color=Red>__递归的缺点__</font>是效率不高，而且使用递归函数需要注意防止栈溢出。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"在计算机中，函数调用是通过<font color=Red>__栈（stack）__</font>这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致<font color=Red>__栈溢出（stack overflow）__</font>。一般默认递归长度在1000左右，使用Python写的递归程序如果递归太深, 那么极有可能因为超过系统默认的递归深度限制而出现错误。 \n",
"\n",
"<font face='楷体' color='blue' size=2> RuntimeError: maximum recursion depth exceeded in comparison </font>\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"解决这个问题有三种方法："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1. 人为设置递归深度，方法如下："
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import sys\n",
"\n",
"\n",
"sys.setrecursionlimit(3000) #括号中的值为递归深度"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"递归深度同时受操作系统栈的深度限制，不同系统环境下，支持的最大递归深度不同。在64位windows 10环境下，最大递归深度约为3900次左右。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"2. 递归改成非递归，用循环的方法实现。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"3. 尾递归优化。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"尾递归优化是解决递归栈溢出的一种方法。\n",
"所谓尾递归是指在函数返回的时候，调用自身，并且return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。\n",
"\n",
"在传统的递归中，典型的模式是，执行第一个递归调用，然后接着调用下一个递归来计算结果。这种方式中途是得不到计算结果，直到所有的递归调用都返回。这样虽然很大程度上简洁了代码编写，但是随着递归的深入，之前的一些变量需要分配堆栈来保存，会导致效率降低。\n",
"\n",
"相对传统递归，尾递归是一种特例。在尾递归中，先执行某部分的计算，然后开始调用递归，所以可以得到当前的计算结果，而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部，所以其有一个优越于传统递归之处，就是无需去保存任何局部变量，减少内存消耗，提高性能。当前时刻的计算值作为第二个参数传入下一个递归，使得系统不再需要保留之前计算结果。理论上讲，没有产生中间变量来保存状态的尾递归，完全可以复用同一个栈帧来实现所有的递归函数操作。这种形式的代码优化就叫做尾递归优化。但是遗憾的是Python本身不支持尾递归（没有对尾递归做优化），而且对递归的次数有限制，当递归深度超过1000时，同样会抛出异常。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"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.7.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
