python-递归

一、斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34
思路：
n位的数等于n-1位和n-2位数之和
使用递归，结束条件n=0和n=1

def f(n):
      if n==0:
            return 0
      if n==1 or n==2:
            return 1
      return f(n-1)+f(n-2)

优化方案，利用字典，来存放计算过的数据

def f(n):
      s={}
      def f1(n):
            if n in s:
                  return s[n]
            else:
                  if n<=2:
                        result=n
                  else:
                        result=f1(n-1)+f1(n-2)
                  s[n]=result
                  return result
       return f1(n)

二、阶乘
利用递归方法求5!。
思路：n! = n*(n-1)!
def f(n): if n==0: return 0 if n==1 or n==2: return 1 return n*f(n-1)
三、生兔子问题
有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
思路：
实际也是斐波那契数列 n个月的兔子数量等于n-1个月的兔子数量+n-2个月的兔子数量
def f(n): if n==1 or n==2: return 1 return f(n-1)+f(n-2)
四、青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
思路：
斐波那契数列问题 跳上n级的方法由跳上n-1级和n-2级方法之和
def f(n): if n==1: return 1 if n==2: return 2 return f(n-1)+f(n-2)
缺点：n大时耗时严重
后续需要优化

五、反转字符串
思路：
循环调用
结束条件 字符串长度为0

def f(n,l):
      if l==0:
            return
      print(n[l-1])
      f(n,l-1)

def f(n):
      def f1(n,i,j):
            if i>j:return n
            else:
                  n[i],n[j]=n[j],n[i]
            return f1(n,i+1,j-1)
      return f1(n,0,len(n)-1)