算法02 - 递归算法

小马哥正在针对Python的所有常见知识进行汇总,更会有大量实战项目不断补充进来.
点击-->全栈工程师养成---Python内容导航页<--查看所有Python内容

掌握递归算法

主要内容

• 什么是递归
• 如何使用递归思维快速编程
• 递归和循环的关系

1. 什么是递归

从前有一座山,山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事: 从前有一座山,山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事: 从前有一座山, 山上有座庙,庙里有个老和尚, 老和尚在给小和尚讲故事:...

上面的例子,是一个没有终点边界的递归,会一直重复下去.

递归的本质是: 一个大规模的问题, 可以使用同样的逻辑处理里面的子问题, 例如, 去银行金库里面取东西, 要经过N道门禁, 做法是: 使用钥匙打开第一道门, 继续打开第二道门, ..., 打开第N到门, 这个时候到达边界, 取出东西, 依次返回. 过程中, 开门就是处理问题的逻辑,开每一道门用的方式都相同.

上面银行的例子就是有边界的递归, 有去有回.

2.如何使用递归快速编程

理解递归编程的本质:

1,定义边界;
2,减少问题规模,使用自身逻辑继续处理问题.

实战例子:

2.1 阶乘

# 定义一个函数,输入一个数字, 返回这个数字的阶乘
def factrial(num):
    if num==1:  #第一步: 设定边界条件
        return 1
    return num*factrial(num-1)  #第二步: 分解问题,将减小规模的问题继续用原有逻辑解决
    #用if表达式(三目运算符)仅一行代码更简洁
    #return 1 if num==1 else num*factrial(num-1)
print(factrial(10))

3628800

# 用循环实现阶乘: 
def factrial(num):
    result = 1
    while num>1:
        result = result * num
        num -= 1
    return result
print(factrial(10))

3628800

2.2 斐波那契数列

def FibonacciSequence(num):
    if num <= 2: # 第一步: 设定边界条件
        return 1
    result = FibonacciSequence(num-1)+FibonacciSequence(num-2)
    num-=1
    return result

print(FibonacciSequence(10))
print([FibonacciSequence(x) for x in range(1,11)])

55
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

# 用循环实现斐波那契数列
def FibonacciSequence(num):
    result = [1,1]
    length = 2
    while length<num:
        result.append(result[length-1] + result[length-2])
        length = len(result)
    return result

print(FibonacciSequence(10))

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

2.3 杨辉三角

待完成...

2.4 回文字符串的判断

2.5 字符串全排列

2.6 二分法查找

2.7 汉诺塔

2.8 二叉树

3.递归和循环的关系

小马哥正在针对Python的所有常见知识进行汇总,更会有大量实战项目不断补充进来.
点击-->全栈工程师养成---Python内容导航页<--查看所有Python内容