Python学习第四十三天—函数9(递归)

Python 3.12.1 (tags/v3.12.1:2305ca5, Dec  7 2023, 22:03:25) [MSC v.1937 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
普通程序员用迭代，天才程序员用递归
递归就是函数调用自身的过程。
一、函数之间可以相互调用
def funA():
    print("Little sister")

   
def funB():
    funA()

   
funB()
Little sister
def func():               （函数调用自己，自己打自己一个耳光）
    print("Little sister")
    func()

   
func()
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
……
Little sisterTraceback (most recent call last):  （无穷无尽的打印，只有用ctrl+c停止，强制退出。）
  File "<pyshell#11>", line 1, in <module>
    func()
  File "<pyshell#10>", line 3, in func
    func()
  File "<pyshell#10>", line 3, in func
    func()
  File "<pyshell#10>", line 3, in func
    func()
  [Previous line repeated 1016 more times]
  File "<pyshell#10>", line 2, in func
    print("Little sister")
RecursionError: maximum recursion depth exceeded
用递归试试打印自己，只不过限制了打印结束条件
def func(i):
    if i>0:            （递归调用一定要有结束条件）
        print("Little sister")
        i -= 1
        func(i)

        
func(10)
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
递归的两个 特点：调用自己；结束条件。
二、求一个数的阶乘。如5！=5×4×3×2×1
（一）先试试迭代的实现方法：
def factIter(n):
    result = n
    for i in range(1,n):
        result *= i
    return result

factIter(5)
120
factIter(10)
3628800
（二）用递归的方法
def factRecur(n):
    if n == 1:
        return 1
    else:
        return n * factRecur(n-1)

   
factRecur(5)
120
理解：factRecur(5)=5* factRecur(4)
          factRecur(4)=4* factRecur(3)
          factRecur(3)=3* factRecur(2)
          factRecur(2)=2* factRecur(1)
          factRecur(1)=1
factRecur(10)
3628800

三、斐波那契数列
（一）先用循环迭代的方法
def fibIter(n):
    a=1
    b=1
    c=1
    while n > 2:
        c=a+b
        a=b
        b=c
        n -= 1
    return c            （这一行可以换成：print(c)）

fibIter(12)
144
（二）同样的需求，采用递归函数实现：
def fibRecur(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibRecur(n-1) + fibRecur(n-2)

   
fibRecur(12)
144
fibRecur(120)        （发现递归效率太低，像死机了一样，事实它还在运算，不知要等到猴年马月，只有用ctrl+c强制终止）
Traceback (most recent call last):
  File "<pyshell#59>", line 1, in <module>
    fibRecur(120)
  File "<pyshell#57>", line 5, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
  File "<pyshell#57>", line 5, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
  File "<pyshell#57>", line 5, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
  [Previous line repeated 102 more times]
  File "<pyshell#57>", line 1, in fibRecur
    def fibRecur(n):
KeyboardInterrupt
fibIter(120)                   （而相比用迭代来实现，一瞬间就完成了）
5358359254990966640871840

补充：用生成器实现斐波那契数列
传参
>>> def fibs(n):
        a=0
        b=1
        while n>0:
                a,b=b,a+b
                n-=1
                yield a

               
>>> list(fibs(12))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

不传参
>>> def fib():
        a=0
        b=1
        while True:
                a,b=b,a+b
                yield a

               
>>> for i in fib():
        if i<100:
                print(i)
        else:
                break

        
1
1
2
3
5
8
13
   
func()
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
……
Little sisterTraceback (most recent call last):  （无穷无尽的打印，只有用ctrl+c停止，强制退出。）
  File "<pyshell#11>", line 1, in <module>
    func()
  File "<pyshell#10>", line 3, in func
    func()
  File "<pyshell#10>", line 3, in func
    func()
  File "<pyshell#10>", line 3, in func
    func()
  [Previous line repeated 1016 more times]
  File "<pyshell#10>", line 2, in func
    print("Little sister")
RecursionError: maximum recursion depth exceeded
用递归试试打印自己，只不过限制了打印结束条件
def func(i):
    if i>0:            （递归调用一定要有结束条件）
        print("Little sister")
        i -= 1
        func(i)

        
func(10)
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
Little sister
递归的两个 特点：调用自己；结束条件。
二、求一个数的阶乘。如5！=5×4×3×2×1
（一）先试试迭代的实现方法：
def factIter(n):
    result = n
    for i in range(1,n):
        result *= i
    return result

factIter(5)
120
factIter(10)
3628800
（二）用递归的方法
def factRecur(n):
    if n == 1:
        return 1
    else:
        return n * factRecur(n-1)

   
factRecur(5)
120
理解：factRecur(5)=5* factRecur(4)
          factRecur(4)=4* factRecur(3)
          factRecur(3)=3* factRecur(2)
          factRecur(2)=2* factRecur(1)
          factRecur(1)=1
factRecur(10)
3628800

三、斐波那契数列
（一）先用循环迭代的方法
def fibIter(n):
    a=1
    b=1
    c=1
    while n > 2:
        c=a+b
        a=b
        b=c
        n -= 1
    return c            （这一行可以换成：print(c)）

fibIter(12)
144
（二）同样的需求，采用递归函数实现：
def fibRecur(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibRecur(n-1) + fibRecur(n-2)

   
fibRecur(12)
144
fibRecur(120)        （发现递归效率太低，像死机了一样，事实它还在运算，不知要等到猴年马月，只有用ctrl+c强制终止）
Traceback (most recent call last):
  File "<pyshell#59>", line 1, in <module>
    fibRecur(120)
  File "<pyshell#57>", line 5, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
  File "<pyshell#57>", line 5, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
  File "<pyshell#57>", line 5, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
  [Previous line repeated 102 more times]
  File "<pyshell#57>", line 1, in fibRecur
    def fibRecur(n):
KeyboardInterrupt
fibIter(120)                   （而相比用迭代来实现，一瞬间就完成了）
5358359254990966640871840

补充：用生成器实现斐波那契数列
传参
>>> def fibs(n):
        a=0
        b=1
        while n>0:
                a,b=b,a+b
                n-=1
                yield a

               
>>> list(fibs(12))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

不传参
>>> def fib():
        a=0
        b=1
        while True:
                a,b=b,a+b
                yield a

               
>>> for i in fib():
        if i<100:
                print(i)
        else:
                break

      
1
1
2
3
5
8
13
21
34
55
89