通用算法-递归入门到放弃

发表于 | 更新于 | 分类于 ， | 阅读次数：

一、前言

递归是编程基础、基础、基础

环境配置如下：

  • 系统：win10
  • 语言：python3.7

二、递归大致分类

  • 分治算法
    • 减而治之（求阶层）：每次将复杂度减一
    • 分而治之（二分查找）：每次将复杂度减半
  • 回溯算法（全排列问题）：如果碰到不符合目标结果的就直接返回
  • 动态规划（与分治算法类似，找最优解）

三、递归思想

（三分实用，七分装逼，总之别人看不懂就完了）

现在就开始讲三分实用

注：如非得已，请勿使用递归，虽然很帅，很漂亮。（如非得已，我的智商也不允许我这么做）

3.1 一个栗子

求n的阶乘，并返回结果。（减而治止）

1
2
3
4
5
6
7
8
def func(n):
    if n == 0:
        return 1

    return n *func(n-1)

if __name__ == '__main__':
    print(func(3))

3.2 递归的目的

目的总结下来就是：大事化小，小事化了

3.3 什么时候可以用递归？

一般来说，有循环的地方就可以用递归，但是递归更加适用于有时候我们并不知道循环多少次，多少层循环，比如二叉树遍历问题（很多问题都可以建模成二叉树问题）。

3.4 递归的主要结构

  • 结束语句：如果没有结束语句，那么递归程序将会一直递归下去。
  • 功能代码：具体要做的事情
  • 返回语句：（也可以没有）

3.5 简单例子

  • 可以看做是一层循环
1
2
3
4
5
6
7
def JustLikeFor(n):
    if n == 0 :
        return
    
    print(n)

    JustLikeFor(n-1)

四、简单实践一

（这些网络上都有很多例子）

4.1 求阶层

问题：求n的阶乘

思路：当求n的阶乘的时候，如果可以每次得到f（n-1）的阶乘就方便了。

设计：当n==0的时候，返回1。（当不知道返回值的时候，就想象最简的时候应该返回什么）

1
2
3
4
5
6
7
8
def func(n):
    if n == 0:
        return 1

    return n * func(n-1)

if __name__ == '__main__':
    print(func(3))

如果使用循环，答案如下：

1
2
3
4
5
6
def func2(n):
    out = 1
    for i in range(1,n+1):
        out = out * i

    return out

4.2 求斐波拉契数列

问题：已知$a_0 = 1, a_1=1, a_n = a_{n-1} + a_{n-2}$，求当n=k时，$a_n$为多少？

思路：如上面求阶层一样，如果每次可以得到$a_{n-1} + a_{n-2}$，就方便了。（减而治之）

设计：当$n=0,1$时，返回为1

1
2
3
4
5
def fun3(n):
    if n == 0 or n == 1:
        return 1

    return fun3(n-1) + fun3(n-2)

注：可以优化，里面会有重复计算的值，可以用一个数组保存起来，碰到计算过的值便不会再计算。（牺牲空间以节省时间）

使用循环来写，可以看出不帅，不简洁，不易读（对懂递归的人来说）

1
2
3
4
5
6
7
8
9
10
11
12
13
def fun4(n):
    if n == 0 or n == 1:
        return 1

    a0 = 1
    a1 = 1
    out = 0
    for i in range(1, n):
        out = a0 + a1
        a0 = a1
        a1 = out

    return out

4.3 求冒泡排序

  • 传统方法：
1
2
3
4
5
6
7
8
9
10
11
12
def maopao(arr):
    n = len(arr)
    if n == 0:
        raise Exception

    for i in range(n):
        for k in range(n - i - 1):
            if arr[k] > arr[k + 1]:
                temp = arr[k]
                arr[k] = arr[k + 1]
                arr[k + 1] = temp
    return arr
  • 递归实现方法一：把递归单纯当做是一层循环来用。此时的结束条件是n == 0，这里使用的是减而治之的思想

(目前没有想到有返回值的方法，除非是使用Class）

1
2
3
4
5
6
7
8
9
10
11
def maopao2(arr, n):
    if n == 0:
        return

    for k in range(n - 1):
        if arr[k] > arr[k + 1]:
            temp = arr[k]
            arr[k] = arr[k + 1]
            arr[k + 1] = temp

    maopao2(arr, n - 1)
  • 递归实现方法二：想个办法再把里面的循环也去了。这里使用的也是减而治之的思想

思路：现在最外层n次循环已经实现了，现在去掉里面的for，换成if判断left和right的大小，使得k每次重新置零1。

1
2
3
4
5
6
7
8
9
10
11
12
13
def maopao3(arr, left, right):
    if right <= 0:
        return

    if arr[left] > arr[left + 1]:
        temp = arr[left]
        arr[left] = arr[left + 1]
        arr[left + 1] = temp

    if left >= (right - 2):
        maopao3(arr, 0, right - 1)           # 控制第一重循环
    else:
        maopao3(arr, left + 1, right)        # 控制第二重循环

4.4 求二分查找

问题：使用二分法遍历数组进行查找，假设数列为由小到大排序。

思路：每次将问题简化一半（分而治之）

设计：当范围不能再划分时，返回，返回值为一个index，认为目标数据就在这个范围之中

1
2
3
4
5
6
7
8
9
10
11
12
def erFen(arr, left, right, goal):
    if left > right:
        return None

    middle = int((left + right) / 2)

    if arr[middle] < goal:
        return erFen(arr, middle + 1, right, goal)  # middle 已经判断过，所以加1
    elif arr[middle] > goal:
        return erFen(arr, left, middle - 1, goal)   # 理由同上
    else:
        return middle                               # 找到了便返回

4.5 求快速排序

问题：使用快速排序2，对乱序数组进行从小到大排序。

思路：每次将问题简化一半（分而治之），对两边单独进行排序，一直递归下去

设计：当范围不能再划分时，返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def getIndex(arr, left, right, tmp):
    if left >= right:
        arr[left] = tmp
        return left

    while (left  < right) and (arr[right] >= tmp):
        right = right - 1

    arr[left] = arr[right]

    while (left < right) and (arr[left] <= tmp):
        left = left + 1

    arr[right] = arr[left]

    return getIndex(arr, left, right,tmp)

def SortByQuickly(arr, left, right):
    if left >= right:
        return

    middle = getIndex(arr, left, right, arr[left])

    SortByQuickly(arr, left, middle - 1)
    SortByQuickly(arr, middle + 1, right)

注：其实getIndex可以使用一个while循环实现，但是为了**，使用递归。

4.6 求归并排序

问题：使用归并排序3，对乱序数组排序。

思路：使用递归将数组不断对半划分，直到不可划分为止，后再进行归并。（出栈后进行数据处理，递归只做数据划分。）

设计：当不可划分的时候，则停止递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def merge(arr, left, middle, right, tmpArray):
    left_i = left
    right_k = right
    temp = middle
    middle = middle + 1
    i = 0

    while (left <= temp) and (middle <= right):   # 扫描两段，比较存入到tmpArray，直到其中一个扫描完毕
        if arr[left] < arr[middle]:
            tmpArray[i] = arr[left]
            left = left + 1
        else:
            tmpArray[i] = arr[middle]
            middle = middle + 1

        i = i + 1

    while left <= temp:     # 把第一段未扫描的结束的直接添加到tmpArray后面
        tmpArray[i] = arr[left]
        left = left + 1
        i = i + 1

    while middle <= right:   # 把第二段未扫描的结束的直接添加到tmpArray后面
        tmpArray[i] = arr[middle]
        middle = middle + 1
        i = i + 1

    i = 0

    while left_i <= right_k: # 复制到原数组中arr
        arr[left_i] = tmpArray[i]
        left_i = left_i + 1
        i = i + 1

def mergeSort(arr, left, right, tmpArray):
    if left >= right:
        return

    middle = int((left + right) / 2)

    mergeSort(arr, left, middle, tmpArray)
    mergeSort(arr, middle + 1, right, tmpArray)

    merge(arr, left, middle, right, tmpArray)


def MergeSort(arr):
    tmpArray = arr[:]  # 复制数组
    mergeSort(arr, 0, len(arr) - 1, tmpArray)
    
    
if __name__ == '__main__':
    arr = [2, 1, 6, 5, 7, 3, 8, 12, 10, 4, 2]
    MergeSort(arr)
    print(arr)

五、简单实践二（二叉树）

（这里主要讲递归，所以二叉树只是辅助，默认原理都懂）

5.1 基本概念

  • 二叉树的储存方式5
    • 数组方式
    • 链表方式（本文主要使用）
  • 二叉树的遍历方式4
    • 前序遍历
    • 中序遍历
    • 后序遍历
    • 层序遍历

5.2 生成测试数据

这里主要是对二叉树进行操作，很多现实问题都可以转换为二叉树遍历问题来进行求解。先生成一个二叉树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Node():
    def __init__(self, data, L_Child=None, R_Child=None):
        self.data = data
        self.L_Child = L_Child
        self.R_Child = R_Child

    def setChild(self, L_Child=None, R_Child=None):
        self.L_Child = L_Child
        self.R_Child = R_Child

def generateRandNode(arr):
    if len(arr) == 0:
        return None

    middle = int(len(arr) / 2)

    return Node(arr[0], generateRandNode(arr[1:middle + 1]), generateRandNode(arr[middle + 1:]))

if __name__ == '__main__':
    arr = [2, 1, 6, 5, 7, 3, 8, 5, 10, 4]
    test = generateRandNode(arr)

在调试模式下可以查看变量，经过验证，len(arr) = 0和len(arr) = n都可以实现分配node

5.1 前序遍历

解释：先遍历左节点，后遍历右节点，在入栈之前操作

  • 方法一
1
2
3
4
5
6
7
8
def FrontTraversing(node):
    if (node == None):
        return

    print(node.data)

    FrontTraversing(node.L_Child)
    FrontTraversing(node.R_Child)
  • 方法二
1
2
3
4
5
def FrontTraversing(node):
    if (node == None):
        return []
    
    return [node.data] + FrontTraversing(node.L_Child)+ FrontTraversing(node.R_Child)

5.2 中序遍历

1
2
3
4
5
def MiddleTraversing(node):
    if (node == None):
        return []
    
    return  FrontTraversing(node.L_Child) + [node.data] + FrontTraversing(node.R_Child)

5.3 后序遍历

1
2
3
4
5
def PostorderTraversal(node):
    if (node == None):
        return []

    return FrontTraversing(node.L_Child) + FrontTraversing(node.R_Child) + [node.data]

5.4 层序遍历

首推使用队列进行进行遍历6，但是这里是递归教学篇，递归也可以实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def levelOrder(node, level, sol):
    if node == None:
        return

    if len(sol) == level - 1:
        sol.append([])

    sol[level - 1].append(node.data)

    levelOrder(node.L_Child, level + 1, sol)
    levelOrder(node.R_Child, level + 1, sol)

def LevelTraversal(node):
    sol = []
    levelOrder(node,1,sol)

    return sol

这里其实使用的是前序遍历类型的方法，但是呢，通过一个参数来确定层数，虽然不是一次把该层遍历完，但是可以把数据储存到对应的层中。

六、题目

  • 迷宫最优路径问题
  • 上台阶问题
  • 计算器实现问题
  • 找最优解问题

百度上面都有答案的

参考文献

1. 排序算法杂谈（二） —— 冒泡排序的递归实现 ↩
2. 快速排序 ↩
3. 排序（7）：归并排序 ↩
4. 二叉树的四种遍历方法笔记 ↩
5. 二叉树存储方式-二叉链表 ↩
6. 数据结构第12讲 二叉树的层次遍历 ↩
-------------本文结束感谢您的阅读-------------
0%