函数调用函数自身，这种方式称为递归，这种函数称为递归函数

递归函数使用过程中，需要找到不变的规律和停止递归的边界条件，因为函数自身调用自身，函数本身的结构不变，只是每次传的参数改变啦

递归实现过程(扩展)：利用栈的思想，先找边界条件，同时将后面的任务存起来，一直到最前面的边界条件，然后回去，每次从栈中取任务，进行计算，一直到最后一个任务取完，结果也计算完毕

递归过程:

• 递归前进段
• 递归边界条件
• 递归返回段

案例讲解

整数转换为字符串

将一个整数转换为字符串，如 345转换为"345"

def trans(num):
    if num // 10 == 0:
        return '%s'%num
    else:
        return trans(num//10)+'%s'%(num%10)

树的高度

递归求二叉树深度

def getHeight(self,root):
    if root is None:
        return 0
    else:
        return max(self.getHeight(root.left), self.getHeight(root.right)) + 1

递归实现吸烟问题

吸烟有危害，不仅仅危害人体健康，还会对社会产生不良的影响。吸烟还很容易引起喉头炎、气管炎，肺气肿等问题； 那么现在假设人一生抽烟10000根达到极限峰值，再抽一根烟就像压倒骆驼的最后一根稻草，会使人体爆发疾病问题； 每天一个人抽烟的个数都比前天多一根（第一天抽一根），且一周只有工作日（周一~周五）会吸烟； 请使用递归的方式求出一个人按照以上方式抽烟达到10000根，爆发疾病需要历经多少天

def smoker(day, count, amount):
    """
    递归解决吸烟问题
    :param day: 当前的天数
    :param count: 当天的吸烟数量
    :param amount: 总计的吸烟数量
    :return: 吸到10000根烟的天数
    """
    if amount >= 10000:
        # 如果吸烟总数大于10000， 返回天数
        return day

    else:
        day += 1 # 每吸一次烟，天数加1
        if day % 7 != 6 and day % 7 != 0:
            # 只有周六，周日不吸烟，判断不是周六，也不是周日
            count += 1 # 当天吸烟的数量
            amount += count # 目前为止，吸烟的总数量

        return smoker(day, count, amount)


print(smoker(1, 1, 1)) # 第1天，吸了1根烟，总共吸了1根烟

青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

# 这个问题，本质是一个斐波那契数列数列求第n项值的问题，如果用递归求，将会超出时间限制
# 因此，直接用循环求即可
class Solution:
    def numWays(self, n: int) -> int:
        a = 1
        b = 1
        for i in range(n):
            a, b = b, a+b
        return a % 1000000007

汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

class Solution:
    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
        n = len(A)
        self.move(n, A, B, C)
    # 定义move 函数移动汉诺塔
    def move(self,n, A, B, C):
        if n == 1:
            C.append(A[-1])
            A.pop()
            return 
        else:
            self.move(n-1, A, C, B)  # 将A上面n-1个通过C移到B
            C.append(A[-1])          # 将A最后一个移到C
            A.pop()                  # 这时，A空了
            self.move(n-1,B, A, C)   # 将B上面n-1个通过空的A移到C