本文共 2321 字，大约阅读时间需要 7 分钟。

递归学习

递归三大要素
第一: 明确函数要干什么
第二: 寻找递归结束的条件
第三: 找出函数等价的关系式

递归求和

方法一

ls=[1,2,3,4,5]def fun(ls,n):    if n==0:        return ls[n]    else:        s=fun(ls,n-1)        return s+ls[n]print(fun(ls,4))

方法二

def fun(ls,n):    if n==len(ls):        return 0    else:        sum=fun(ls,n+1)        return sum+ls[n]print(fun(ls,0))

递归判断字符串的内容是否相同

a="abcdef"b="abcdef"def fun(a,b):    if len(a)==0:        return True    if len(a)!=len(b):        return False    if a[0]!=b[0]:        return False    else:        return fun(a[1::],b[1::])print(fun(a,b))

斐波那契数列

1、1、2、3、5、8、13、21、34

def fun(n):	#递归退出条件, 当n是第一个数,或者第二个数, 返回1    if n==1 or n==2:        return 1    else:    	#第三个数就等于前两个数的和        return fun(n-2)+fun(n-1)

求在m个球中, 一次性取n个球, 不放回有多少种取法

#在m个球中, 取n个,不放回,有多少中取法def fun(m,n):    #如果一次性取的球大于剩余的球, 则没有取法    if m<n:        return 0    #如果相等, 则只有一种取法    if m==n:        return 1    #如果n等于0, 则只要一种取法就是不取    if n==0:        return 1    else:        #想象m个球中有一个特殊球,取法划分,是否包含这个特殊球        # fun(m-1,n-1)不包含+fun(m-1,n)包含的两种方式加起来, 就是一共多少种取法        return fun(m-1,n-1)+fun(m-1,n)print(fun(10,3))

求n个元素的全排列

def fun(s,k):    if k==len(s):        for i in s:            print(i,end='')        print()    for i in range(k,len(s)):        s[i],s[k]=s[k],s[i]        fun(s,k+1)        s[i], s[k] = s[k], s[i] #回溯s="ABC"ls=list(map(str,str(s)))fun(ls,0)

求两个字符串的公共最长的公共子序列的长度

# abcd  bcds1=input().strip()s2=input().strip()def f(s1,s2):    if len(s1)==0 or len(s2)==0:        return 0    if s1[0]==s2[0]:        return f(s1[1::],s2[1::])+1    else:        return max(f(s1[1::],s2),f(s1,s2[1::]))print(f(s1,s2))

使用递归将字符串反转

s1=input().strip()def fun(s):    if len(s)<=1:        return s    else:        return fun(s[1::])+s[0]print(fun(s1))

使用递归打印杨辉三角

def f(m,n):    if n==0 or m==n:        return 1    else:        return f(m-1,n)+f(m-1,n-1)n=int(input().strip())for i in range(n):    for j in range(n-i-2,-1,-1):        print(" ", end='')    for j in range(i+1):        print(f(i,j),end=' ')    print()

m个A,n个B 可以组成多少组排列

def f(m,n):    if m==0 or n==0:        return 1    else:        return f(m-1,n)+f(m,n-1)m,n=map(int,input().split())print(f(m,n))

求最大公约数

def f(x,y):    if x<0:        x=-x    if y<0:        y=-y    if y==0:        return x    return f(y,x%y)  #最大公约数 <辗转相除法>a=15b=60while True:    if a==0:        print(b)        break    a,b=b%a,a