12 递归

变量解析 LEGB

In [4]: x = 5
In [5]: def foo(x =6, y=7):
   ...:     nonlocal x
  File "<ipython-input-5-89de33a38c80>", line 2
    nonlocal x
    ^
SyntaxError: name 'x' is parameter and nonlocal
In [6]: def foo(x = 6, y=7):
   ...:     def foo2(a=10, b=11):
   ...:         nonlocal x
   ...:         x = 5
   ...:         return x
   ...:     return x
   ...:
In [7]: foo(6, 7)
Out[7]: 6
In [8]:
In [8]: foo(y=7)

python 递归函数

import dis
dis.dis('''
def foo1(b, b1=3):
'''
函数执行过程字节码
'''
    print('foo1 called', b, b1)
    foo2(2)
def foo2(a):
    pass
''')

编写递归程序：
a. 直接/间接调用自身
b. 递归需要有边界条件，递归前进段，递归返回段
c. 一定要有边界条件
当边界不满足时候，递归前进
当边界满足的时候，递归返回

python关于递归的限制
import sys
sys.getrecursionlimit()
sys.setrecursionlimit()

使用递归打印斐波那契数列

1. 使用循环打印
   pre = 0
   cur = 1
   print(pre, cur, end = ‘ ‘)
   n = 10
   for i in range(2, n):
   pre, cur = cur, pre + cur
   print(cur, end = ‘ ‘)
   def pfib(n):
   pre = 0
   cur = 1
   print(pre, cur, end =’ ‘)
   for i in range(n-2):
   pre, cur = cur, pre+cur
   print(cur, end = ‘ ‘)
2. 使用递归函数打印
   def fib(n):
   ‘’’
   f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2)
   ‘’’
   if n == 0: return 0
   if n == 1: return 1
   return fib(n-1) + fib(n-2)
   def fib2(n):
   return 1 if n < 2 else fib2(n-1) + fib2(n-2)
   def fib3(n, pre=0, cur=1):
   ‘’’类似循环，n为边界’’’
   pre, cur = cur, pre+cur
   print(cur, end=’ ‘)
   if n == 1:
   return
   fib3(n-1, pre, cur)

fib函数时间复杂度O(2N)

'''递归练习代码'''
def fib5(n, pre=0, cur=1):
    if pre == 0: print(pre,cur, end = ' ')
    pre, cur = cur, pre+cur
    print(cur, end =' ' )
    if n == 2: return
    fib5(n-1, pre, cur)
In [134]: fib5(10)
0 1 1 2 3 5 8 13 21 34 55
def fib6(n, pre=0, cur=1):
    if pre == 0: print(pre, cur, end = ' ')
    pre, cur = cur, pre+cur
    print(pre, end = ' ')
    if n == 2: return
    fib6(n-1, pre, cur)
fib6(10)
def fib6(n, pre=0, cur=1):
    if pre == 0: print(pre, end = ' ')
    pre, cur = cur, pre+cur
    print(pre, end = ' ')
    if n == 2: return
    fib6(n-1, pre, cur)
fib6(10)

base64_table
0 ~25 A~Z
26~51 a~z
52~61 0~9
62 +
63 /