一、阶乘 n = 1x2x3x4x5x....xn
```
def jiecheng(n):
if n == 1:
return 1
else:
return n*jiecheng(n-1)
n= int(input('请输入n的值n='))
A= jiecheng(n)
print(f'{n}的阶乘n!={A}')
```
或者采用reduce函数---reduce() 函数会对参数序列中元素进行累积。函数将一个数据集合（链表，元组等）中的所有数据进行下列操作：用传给 reduce 中的函数 function（有两个参数）先对集合中的第 1、2 个元素进行操作，得到的结果再与第三个数据用 function 函数运算，最后得到一个结果。
from functoolsimport reduce
n= int(input('请输入n的值n='))
b= reduce(lambda x, y: x*y, range(1, n+1))
print(f'{n}的阶乘n!={b}')
二、使用递归编写一个power()函数来进行幂运算，也就是说power(x,n)返回x的n次幂的值。y=x^n
def power(x,n):
if n == 0:
return 1
else:
return x*power(x,n-1)
x= int(input('请输入x的值x='))
n= int(input('请输入n的值n='))
A= power(x,n)
print(f'{x}的{n}次幂的值为{A}')
三、斐波那契数列
已知一个数列：1、1、2、3、5、8、13、。。。。的规律为从3开始的每一项都等于其前两项的和，这是斐波那契数列。求满足规律的100以内的所以数据.
a= 0
b= 1
while b< 100:
print(b, end=",") ##print(a, end=",") 的话，是从0开始。最后一个少一个数
a, b= b, a+b
四、用欧几里得算法求两个数的最大公约数～
# 简易版
def Common_divisor(x,y):
if x % y == 0:
return y
else:
t= x % y
return Common_divisor(y,t)
print(Common_divisor(24,16))
# 高级版
def Common_divisor(x,y):
if y:
return Common_divisor(y, x % y)
else:
return x
print(Common_divisor(24,16))
五、汉诺塔问题
# 汉诺塔：汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
# 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘
# 当只有一个盘子的时候，只需要从将A塔上的一个盘子移到C塔上。
# 当A塔上有两个盘子是，先将A塔上的1号盘子(编号从上到下)移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上。
# 当A塔上有3个盘子时，先将A塔上编号1至2的盘子(共2个)移动到B塔上(需借助C塔)，然后将A塔上的3号最大的盘子移动到C塔，最后将B塔上的两个盘子借助A塔移动到C塔上。
# 当A塔上有n个盘子是，先将A塔上编号1至n-1的盘子(共n-1个)移动到B塔上(借助C塔)，然后将A塔上最大的n号盘子移动到C塔上，最后将B塔上的n-1个盘子借助A塔移动到C塔上。
# 综上所述，除了只有一个盘子时不需要借助其他塔外，其余情况均一样(只是事件的复杂程度不一样)。
def hanno(n, a, b, c):
# '''汉诺塔问题'''
if n == 1:
print(a, '-->', c)
else:
hanno(n - 1, a, c, b)
print(a, '-->', c)
hanno(n - 1, b, a, c)
hanno(5, 'A', 'B', 'C')
print(hanoi(3,A,B,C))
六、如何从一个有序列表的1000个元素里面找到674这个元素的索引
# data = [1,3,5,9,10,25,27,39.........674,698................]
分析：
1、将列表从中间的位置分为2个部分；
2、找到列表的中间位置的值，若此值小于674，说明674在后面的那一部分。若大于674，说明在前面那一部分；
3、递归列表，重复将列表从中间位置分为2个部分，直到中间位置的值等于674，返回它的索引；
#列表中找到其中一个值，并返回其索引
比如：
seq= [1,2,4,5,9,8,10,24,27]
seq.sort() #先将列表重新排序，得到一个有序的列表
def search(seq,n,lower,upper): #seq列表，n要找的数据，lower列表的索引下限，upper索引上限
middle= (lower + upper)//2 #找到列表的中间位置
if n > seq[middle]: #找到列表的中间位置的值，对比n，若比n小。则在中间位置后面找，如n为60，中间为50，则在50+后面找
return search(seq,n,middle+1,upper) #递归search，将结果返回再找一次
elif n < seq[middle]: #找到列表的中间位置的值，对比n，若比n大。则在中间位置前面找，如n为20，中间为50，则在50前面找
return search(seq,n,lower,middle)
else: #当n等于中间值的时候，即已找到该元素，返回其索引值即可
return middle
print(search(seq,5,0,8)) # 输出结果：3
七、创建一一个函数，用来检查一个任意的字符串是否是回文字符串 ,如果是返回True,否则返回False（这道题跟第六题差不多思维）
#回文字符串,字符串从前往后念和从后往前念是一样的#abcba
#先检查第一个字符和最后一个字符是否一致，如果不一致则不是回文字符串
#检查abcdefgfedcba是不是回文
#检查bcdefgfedcb 是不是回文
#检查cdefgfedc 是不是回文
#检查defgfed 是不是回文
#检查efgfe是不是回文
#检查fgf是不是回文
#检查g是不是回文
# 递归
def fn(s):
if len(s)<2:
return True
# print(s)
elif s[0] != s[-1]:
return False
return fn(s[1:-1])
print(fn('abcba'))
# 另一种解法
def is_palindrome(n, start, end):
if start > end:
return 1
else:
return is_palindrome(n, start + 1, end - 1) if n[start] == n[end] else 0
string= input('请输入一串字符串：')
length= len(string) - 1
if is_palindrome(string, 0, length):
print('"%s"是回文字符串!' % string)
else:
print('"%s"不是回文字符串!' % string)
八、猴子吃桃
第一天摘下若干个桃子，当即吃了一半，又多吃了一个；第二天将剩下的桃子吃掉一半，又多吃1个；
第三天第四天均是如此，# 到第五天想吃时，只剩下1个。 # 编写程序计算猴子第一天共摘了多少个桃子。
分析：
第5天的数量=1；
第4天的数量=（第5天数量+1）*2
第3天的数量=（第4天数量+1）*2
第2天的数量=（第3天数量+1）*2
第1天的数量=（第2天数量+1）*2
(公式F(n-1)=(F(n)+1)*2)=>F(n)=[F(n+1)+1]*2
def F(n):
if n == 5 :
return 1
else:
return (F(n+1)+1)*2
print(F(1)) #输出结果：46
优化一下：
def F(n):
if n==5:
return 1
return (F(n+1)+1)*2
print(F(1))
九、返回1+2+3+4+5+n的和
#递归
def F(n):
if n == 1:
return 1
return n+F(n-1)
print(F(100))
十、打印*
***
**
*
#递归
def F(n):
if n ==1:
print('*')
else:
print('*'*n)
F(n-1)
F(5)
十一、使用递归编写一个十进制转换为二进制的函数（要求采用“取2取余”的方式，结果与调用bin()一样返回字符串形式）：
def DecToBin(dec):
result= '' #定义一个空的字符串
if dec:
result= DecToBin(dec // 2)
return result+ str(dec % 2)
else:
return result
print(DecToBin(33)) # 100001
十二、写一个函数get_digits(n)，将参数n分解出每个位的数字并按顺序存放到列表中。举例：get_digits(12345) ==> [1, 2, 3, 4, 5]：
result= []
def get_digits(n):
if n > 0:
result.insert(0, n%10)
# print(result)
get_digits(n//10)
get_digits(12345)
print(result) # [1, 2, 3, 4, 5]
# 或者采用append()函数
result= []
def get_digits(n):
if n > 0:
result.append(n%10)
# print(result)
get_digits(n//10)
new_result= result[::-1]
return new_result
A= get_digits(12345)
print(A)
十三、有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。
问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？：
def age(n):
if n == 1:
return 10
else:
return age(n - 1) + 2
print('哈哈，我知道了，第五个人的年龄是 %d 岁，啵啵脆！' % age(5)) # 18岁
（经典）十四、题目：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？
第10次掉下所经过的总距离实际上就是前9次掉下经过的总距离再加上弹起来一次再加掉下去一次。
第n次掉下去的高度总是等于n-1次弹起来的高度，所以我们在程序中只需要计算出n-1次掉落后弹起来的高度，结果就可以出来了。
如题我们知道第一次掉下的高度为100，弹起来的是50，也就是(100/2)；第二次掉下去的是50，弹起来的是25(也就是100/2²)，
第三次掉下去的是25，弹起来的是12.5(也就是100/2³)...那么，第n次弹起来的高度就是100/2ⁿ。
假入说设我们要求的次数为n，也就是我们要计算第n-1次弹起来的高度，才能得出第n次掉下去的高度。
另外，题目中还要求算出第10次掉下去再弹起来多高，这个很简单，就是n-1次弹起来的高度÷2即可。
# 定义一个类，里面有两个方法，一个用来计算反弹高度，一个用来计算经过了多少米。
class ball_pop(object):
def __init__(self,times):
self.times= times
self.init_height= 100
# 获取距离方法
def __get_distance(self,n):
if n == 1:
return self.init_height
return self.__get_distance(n-1)+self.init_height/2**(n-1)*2
# def get_distance(self): 从外部无参数计算总距离的备用方法
# return self.__get_distance(self.times)
# 获取n次反弹高度的方法
def __get_ntimes_popup(self):
return self.init_height/2**(self.times-1)/2
# 打印
def __call__(self):
print(f"小球第{self.times}次落下后经过的总距离为{self.__get_distance(self.times)}米, 第{self.times}落下后再弹起来的高度为{self.__get_ntimes_popup()}米")
ball= ball_pop(10)
ball()
# 输出结果：小球第10次落下后经过的总距离为299.609375米, 第10落下后再弹起来的高度为0.09765625米
十五、二分查找（其实就是中间数查找，与第六题差不多）
def two_find(lst, aim, start = 0 ,end = None):
end= len(lst) if end is None else end
mid_index= (end - start) // 2 + start # 计算中间值
if start > end:
return None
elif lst[mid_index] < aim:
return two_find(lst, aim, start = mid_index+ 1, end = end )
elif lst[mid_index] > aim:
return two_find(lst, aim, start = start, end = mid_index-1)
else:
return mid_index
lst= [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
while 1:
num= input('请输入要查找的数：')
if num.upper() == 'Q': # 输入q退出查找程序
print('结束查找！')
break
else:
num= int(num)
ret= two_find(lst,num)
if ret== None:
print('找不到“{}”这个值！'.format(num))
else:
print('找到了，“{}”的位置是“{}”'.format(num, ret))
另一个方法：
# def binary_chop(alist, data):
# """
# 递归解决二分查找
# 1. 二分查找是有条件的，首先是有序，其次因为二分查找操作的是下标，所以要求是顺序表
# 2. 最优时间复杂度：O(1)
# 3. 最坏时间复杂度：O(logn)
# :param alist:
# :return:
# """
# n = len(alist)
# if n < 1:
# return False
# mid = n // 2
# if alist[mid] > data:
# return binary_chop(alist[0:mid], data)
# elif alist[mid] < data:
# return binary_chop(alist[mid+1:], data)
# else:
# return True
#
# if __name__ == '__main__':
# lis = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
# if binary_chop(lis, 12):
# print('ok')
十六、三级菜单
menu= {
'北京': {
'朝阳': {
'国贸': {},
'CICC': {},
'HP': {},
'渣打银行': {},
'CCTV': {},
},
'望京': {
'陌陌': {},
'奔驰': {},
'360': {},
},
'三里屯': {
'优衣库': {},
'apple': {},
},
'昌平': {
'沙河': {
'老男孩': {},
'阿泰包子': {},
},
'天通苑': {
'链家': {},
'我爱我家': {},
},
'回龙观': {},
},
'海淀': {
'五道口': {
'谷歌': {},
'网易': {},
'sohu': {},
'快手': {},
},
'中关村': {
'youku': {},
'Iqiyi': {},
'汽车之家': {},
'新东方': {},
'QQ': {},
},
},
},
'上海': {
'浦东': {
'陆家嘴': {
'CICC': {},
'高盛': {},
'摩根': {},
},
},
'闵行': {
'人民广场':{
'炸鸡店': {},
'地铁站':{},
'奶茶店':{},
'杜莎夫人蜡像馆':{},
},
},
'静安': {
'南京西路':{
'静安寺':{},
'静安公园':{},
'静安地铁站':{},
},
},
},
'山东': {
'济南': {
'历下区':{
'趵突泉':{},
'千佛山':{},
'红叶谷':{},
'大明湖公园':{},
},
},
'德州': {
'乐陵': {
'丁务镇': {},
'城区': {},
},
'平原': {
'千佛塔':{},
'琵琶湾公园':{},
'文昌阁':{},
},
},
'青岛': {
'市北区':{
'青岛啤酒':{},
'北岭山森林公园':{},
'人民政府':{},
'海泊河公园':{},
},
},
'潍坊':{
'潍城区':{
'植物园':{},
'富华游乐园':{},
'白浪绿洲湿地公园':{},
},
},
},
}
#递归方法：
def threeLM(dic):
while True:
for kin dic:print(k)
key= input('请输入地址【返回/b,退出/q】input>>>').strip()
if key== 'b' or key== 'q':return key
elif keyin dic.keys() and dic[key]:
ret= threeLM(dic[key])
if ret== 'q':return 'q'
threeLM(menu)
其他方法：（堆栈：）
l=[menu]
while True:
for keyin l[-1]:print(key)
k=input('input>>>').strip()
if kin l[-1].keys() and l[-1][k]:
l.append(l[-1][k])
if k=='b':l.pop()
if k=='q':break
else:continue
或者：
floor= menu# 定义当前层为menu，实现动态循环；
empty_list= [] # 定义一个空列表，保存所有父级，最后一个元素永远是父级；
while True:
for kin floor:
print(k) #打印菜单内容
# 让用户选择输入，strip()方法用于移除字符串头尾指定的字符(默认为空格或换行符)或字符序列；
choice= input('input>>【返回/b】，退出/q：').strip()
if choice== 'q': # 判断如果用户输入q，便break跳出循环
break
# if choice == 'b':
# # return choice
# 判断用户如果输入的字符长度如果为0，便跳过本次循环；
if len(choice) == 0: #len()方法返回对象(字符、列表、元祖等)长度或项目个数。
continue
if choicein floor: # 如果用户输入的是菜单里的内容
#在进入下一层之前，把当前层追加到列表中；
# 下一次循环时，如果用户输入b，就可以直接取列表的最后一个值出来；
empty_list.append(floor) #append()方法用户在列表末尾添加新的对象；
floor= floor[choice] #改成下一层
elif choice== 'b': # 用户如果输入b
if empty_list: # 判断列表是否为空
# pop()函数用于移除列表中的一个元素(默认最后一个元素)，并且返回该元素的值
floor= empty_list.pop() # 取出列表最后一个值，因为他就是当前层的父级
else:
print('您的输入有误!')
十七、问题：要求利用递归函数调用的方式，将获取到所输入的5个字符，以相反顺序分别输出来。
def output(s, l):
if l == 0:
return
print(s[l - 1],end='')
output(s, l - 1)
s= input('请输入一个字符串:')
l= len(s)
output(s, l)
＃输入：123456789 输出：987654321
十八、写出python程序，一定要利用递归函数，尽量不用for循环、while循环。
输入整数B代表进制数，再输入两个B进制的数，用列表list_a和list_b表示，输出list_a+list_b的B进制数结果，也可以用列表来表示。
例如，B=16，输入list_a=[10,9,9]和list_b=[9,9]，相加后的十六进制结果是[11,3,2]；如果B=11，相加后的结果是[1,0,8,7]。
def fun(mod, lst_a, lst_b, carry=0): # carry为进位数
result= [] # 每次递归的计算结果列表
if lst_a and lst_b: # 如果列表均不为空
sum= lst_a[-1] + lst_b[-1] + carry # 取出每个列表最后一个元素与上一层传入的进位数相加求和
lst_a.pop(-1) # 从列表中去除最后一个元素
lst_b.pop(-1) # 从列表中去除最后一个元素
elif lst_a: # 如果只有lst_a列表不为空
sum= lst_a[-1] + carry # 列表最后一位元素与上一层传入的进位数相加求和
lst_a.pop(-1) # 从列表中去除最后一个元素
elif lst_b: # 如果只有lst_b列表不为空
sum= lst_b[-1] + carry # 列表最后一位元素与上一层传入的进位数相加求和
lst_b.pop(-1) # 从列表中去除最后一个元素
else: # 如果列表均为空
if carry: # 如果有进位数
return [carry] # 返回进位数
else: # 否则
return [] # 返回空列表
carry= sum// mod # 计算当前和按进制计算后的进位数
remainder= sum% mod # 计算当前和按照进制计算后的余数
result= [remainder] + result# 余数以列表形式与外层递归列表合并
return fun(mod, lst_a, lst_b, carry=carry) + result# 进行下一层递归
list_a= [10, 9, 9]
list_b= [9, 9]
mod= int(input('请输入代表进制数的B的值B='))
print(f'list_a+list_b后{mod}进制的结果为:{fun(mod, list_a, list_b, carry=0)}')
输出结果：
请输入代表进制数的B的值B=16
list_a+list_b后16进制的结果为:[11, 3, 2]
十九、list = [{‘name’:’小红’,sub’:[{‘name’:’小明’,’sub’:[{‘name’:’小花’}]}，{’name‘:’小黑’}]}]
这是一个嵌套列表，但是嵌套的可能有n层，如何运用递归函数得到列表中所有的“name”值，
并且有层级关系的名字需要拼接起来，得到的结果是“[‘小红’，’小红’/’小明，’小红’/’小明/’小花’, ‘小红’/’小黑’]” 。
解题思路：
因为外层的名字要与内层名字拼接，所以每次获取外层的名字，都要作为参数传入内层，最外层参数默认为空字符串；每一次将外层名字与当前层名字拼接后，都判断是否存在下一层，如果存在则将下一层的列表和当前层的拼接结果作为参数进行递归，并将递归结果与当前结果列表合并。
lst= [{'name': '小红', 'sub': [{'name': '小明', 'sub': [{'name': '小花'}]}, {'name': '小黑'}]}]
def fun(lst, name=''): # 参数“name”为已从字典中取出的键值
result= [] # 每次递归的结果列表
for dicin lst: # 从列表获取字典
if name: # 如果有上一次递归结果
names= name + '/' + dic['name'] # 上一次递归结果连接当前字典“name”键的值
else:
names= dic['name'] # 直接将当前字典“name”键的值存入
result.append(names) # 结果列表中添加当前递归结果
sub= dic.get('sub', None) # 获取子级列表
if sub: # 如果存在子级列表
result= result+ fun(sub, names) # 当前结果列表与子级结果列表合并
return result# 返回每次递归结果列表
print(fun(lst))
