python—递归函数

递归函数

定义：即在函数定义中自己调用自己

• 递归就是在过程或函数中自我调用
• 递归必须有递归出口，即递归结束条件

---

举个栗子—阶乘：

def fact(n):

    if n == 1:

        return 1

    return n * factorial(n - 1)

print(factorial(5))

# 120

函数执行过程：

---

尾递归优化：

# 尾递归的例子

def calc(n):

    print(n - 1)

    if n > -50:

        return calc(n-1)

根据尾递归定义，我们的阶乘就不是尾递归了

def fact(n):

    if n == 1:

        return 1

    return n * factorial(n - 1)

因为返回语句是一个乘法操作 ，return n * factorial(n - 1) 引入了乘法操作。

---

汉诺塔问题

def move(n,a,b,c):

    if n == 1:

        print('move', a, '-->', c)

    else:

        move(n-1,a,c,b)

        move(1,a,b,c)

        move(n-1,b,a,c)

move(3,'A','B','C')

# 打印结果：

# move A --> C

# move A --> B

# move C --> B

# move A --> C

# move B --> A

# move B --> C

# move A --> C