递归的定义

函数作为一种代码封装，可以被其他程序调用，当然，也可以被函数内部代码调用。这种函数定义中调用函数自身的方式称为递归。就像一个人站在装满镜子的房间中，看到的影像就是递归的结果。递归在数学和计算机应用上非常强大，能够非常简洁的解决重要问题。

以求阶乘为例

#计算阶乘：根据用户输入的整数n，计算并输出n的阶乘值。
def fact(n):#计算阶乘if n == 0:return 1else:return n * fact(n-1)num = eval(input("请输入一个正整数: "))
print(fact(num))

递归函数调用过程 

递归的思想

把规模大的问题转化为规模小的、具有与原来问题相同解法的问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。

递归的使用方法

1. 找到递归关系，即把一个复杂的问题转化为与它形式相似、但规模较小的问题
2. 找到递归出口，即问题转化时，当规模足够小，可以直接求解

---

递归法练习

1.字符串反转      

对于用户输入的字符串s，输出反转后的字符串。解决这个问题的基本思想是把字符串看作一个递归对象。    

def rev(s):  # 反转字符串if len(s) == 1:return selse:return s[-1]+rev(s[:len(s)-1])s = input()
print(rev(s))

---

2.斐波那契数列（1、1、2、3、5、8、13、21、34、……）

兔子繁殖问题：

在700多年前，意大利著名数学家斐波那契在《算盘全集》中提到这样一个问题：一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死，请问第1个月出生的一对兔子，第n个月有多少对兔子？

F(1)=1

F(2)=1

F(3)=F(1)+F(2)=1+1=2

F(4)=F(2)+F(3)

…………

F(N)=F(N-2)+F(N-1)

代码

def fab(n):if n <= 2:return 1else:return fab(n-1)+fab(n-2)n = eval(input())
print(fab(n))

 斐波那契的递归实现版本里面有很多冗余计算，可以通过增加缓存来优化。

# -*- coding: UTF-8 -*-
# 斐波那契数列 递归
def fibonacci_inner(n, cache):if n == 1 or n == 2:return 1r = 0# 实现缓存if cache.get(n) is not None:return cache[n]else:cache[n] = fibonacci_inner(n-1, cache) + fibonacci_inner(n-2, cache)return cache[n]def fibonacci(n):return fibonacci_inner(n, {})if __name__ == '__main__':n = eval(input())print(fibonacci(n))

---

3.赶鸭子问题

题目描述

一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？

分析

设经过的村子为n (n = 0,1,2,...,7)，根据题目分析可知递归结束的出口: n = 7时，剩余鸭子数duck = 2;

分析递归体：从后向前推 n=7时 ，duck = 2， 由于每经过一个村子，卖去所赶鸭子的一半又一只，因此七个村子后剩余的鸭子数 duck[7]=duck[6]-(duck[6]/2+1)

反推duck[6] = (duck[7] + 1) * 2

最终递归体: (duck[n+1] + 1) * 2;

综上  

n=7	duck=2
0<=n<7	duck=(duck(n+1) + 1) * 2

代码

def duck(n):if n == 7:return 2else:return (duck(n+1)+1)*2print("鸭子的总数为:{}".format(duck(0)))
sum = duck(0)
for i in range(1, 8):print("第{}个村庄卖出{}只鸭子，剩余鸭子数为{}". format(i, sum-duck(i), duck(i)))sum = duck(i)

运行结果

---

4.角谷定理

题目描述

角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。

示例	输入	输出
示例1	22	11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 step=15
示例2	33	16 8 4 2 1  step=5

问题分析

递归出口：当输入的数字为1时，则直接输出

递归体：当输入数据不为1时

• 当数据为偶数：除以2,递归直到数据为1，输出
• 当数据为奇数：乘3再加1，递归直至数据为1，输出

# 角谷定理
def jiaogu(step, n):if n == 1:return stepelse:if n % 2 == 0:step += 1print("{:.0f}".format(n/2), end=" ")return jiaogu(step, n/2)else:step += 1print("{:.0f}".format(n*3+1), end=" ")return jiaogu(step, n*3+1)n = eval(input())
m = jiaogu(0, n)
print("\n需要经过{}次运算".format(m))

5.分橘子问题

题目描述

日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？

分析：

老大得到老六分给的桔子后，每个人的桔子总数为总数的平均即2520/6=420个

针对老大所得桔子数 = (420 - 从老六那里所得桔子数)*8/7, 老六分给老大其1/3之后剩余420个，因此他有420*3/2 = 630个桔子，即分给老大210个

则可以算出老大在得到老六桔子之前有420-210 = 210个由于老大将其1/8分给老二，则可算出老大最初拥有240个桔子

......

代码

'''
n  表示第几个儿子
beforenum  表示分配之前的橘子数
afternum  表示分配之后的橘子数
m  表示分配的比例
'''def orange(n, beforenum, afternum, m):if n > 6:return 0else:print("老" + str(n) + "原有橘子数" + str(beforenum) + "个")# 分给下一个人的橘子数givenum = afternum / m# 下一个人的橘子数nextbeforenum = 420 * (m - 1) / (m - 2) - givenum# 下一人加上之前的橘子数的总数aftergetnum = nextbeforenum + givenumreturn orange(n + 1, nextbeforenum, aftergetnum, m - 1)orange(1, 240, 240, 8)

运行结果

---