递归思想在算法与数据结构中发挥到的作用

文章目录

• • 递归思想
  • 什么情况下使用递归
  • 案例总结

递归思想

  递归是在算法求解中比较常见的一种求解思路，通过自身调用，递归能够减少我们在程序中书写很多逻辑代码，在有些场景下，能够实现for和while不能达到的目的。 递归的基本原理是: 每次自身调用时都会在本地栈复制一份作用域出来，存放变量和参数， 自身调用一次相当于压栈一次，返回和就弹出栈，直到调用结束，也就意味着栈也被清空。

什么情况下使用递归

  1. 比较多的嵌套结构。比如多嵌套列表结构: [1, 2, 3, 4, [5, 6, [7, 8]]]， 求 列表中所有数据的和。
  2. 树的遍历。我们可以按照先根遍历来获取树的整个结构， 例如: 制作目录树。
  3. 有规律的线性序列求解。 比如,斐波那契数列等。

案例总结

1. 求 a = [1, 2, 3, 4, [5, 6, [7, 8]]] 中所有元素的和。

def func(list_data):
    sum_data = 0
    for i in list_data:
        if not isinstance(i, list):
            sum_data += i
        else:
            sum_data += func(i)
    return sum_data

print(func(a))

打印结果: 36

2. 求斐波那契数列第n项数值

def func(number):
    if number == 1 or number == 2:
        return 1
    else:
        return func(number - 1) + func(number - 2)

3. n的阶乘问题

def func(number):
    if number == 1:
        return number
    else:
        return number * func(number - 1)

4. 多级目录树问题，目录的根为多个或者一个，目录的级别从一级到多级。

例如，使用如下结构生成目录:

{
    "data": [
        {
            "id": 1,
            "parent_id": null
        },
        {
            "id": 2,
            "parent_id": 1
        },
        {
            "id": 3,
            "parent_id": null
        },
        {
            "id": 4,
            "parent_id": 3
        },
        {
            "id": 5,
            "parent_id": 4
        },
        {
            "id": 6,
            "parent_id": 4
        },
        {
            "id": 7,
            "parent_id": 3
        },
        {
            "id": 8,
            "parent_id": 7
        },
        {
            "id": 9,
            "parent_id": 7
        },
        {
            "id": 10,
            "parent_id": 7
        },
        {
            "id": 11,
            "parent_id": 3
        },
        {
            "id": 12,
            "parent_id": 11
        },
        {
            "id": 13,
            "parent_id": 11
        },
        {
            "id": 14,
            "parent_id": 11
        },
        {
            "id": 15,
            "parent_id": 11
        },
        {
            "id": 16,
            "parent_id": 11
        },
        {
            "id": 17,
            "parent_id": 3
        },
        {
            "id": 18,
            "parent_id": 17
        },
        {
            "id": 19,
            "parent_id": 17
        },
        {
            "id": 20,
            "parent_id": 17
        }
    ]
}

dict_data = {
    "data": [
        {
            "id": 1,
            "parent_id": None
        },
        {
            "id": 2,
            "parent_id": 1
        },
        {
            "id": 3,
            "parent_id": None
        },
        {
            "id": 4,
            "parent_id": 3
        },
        {
            "id": 5,
            "parent_id": 4
        },
        {
            "id": 6,
            "parent_id": 4
        },
        {
            "id": 7,
            "parent_id": 3
        },
        {
            "id": 8,
            "parent_id": 7
        },
        {
            "id": 9,
            "parent_id": 7
        },
        {
            "id": 10,
            "parent_id": 7
        },
        {
            "id": 11,
            "parent_id": 3
        },
        {
            "id": 12,
            "parent_id": 11
        },
        {
            "id": 13,
            "parent_id": 11
        },
        {
            "id": 14,
            "parent_id": 11
        },
        {
            "id": 15,
            "parent_id": 11
        },
        {
            "id": 16,
            "parent_id": 11
        },
        {
            "id": 17,
            "parent_id": 3
        },
        {
            "id": 18,
            "parent_id": 17
        },
        {
            "id": 19,
            "parent_id": 17
        },
        {
            "id": 20,
            "parent_id": 17
        }
    ]
}

import json

dict_data = {
    "data": [
        {
            "id": 1,
            "parent_id": None
        },
        {
            "id": 2,
            "parent_id": 1
        },
        {
            "id": 3,
            "parent_id": None
        },
        {
            "id": 4,
            "parent_id": 3
        },
        {
            "id": 5,
            "parent_id": 4
        },
        {
            "id": 6,
            "parent_id": 4
        },
        {
            "id": 7,
            "parent_id": 3
        },
        {
            "id": 8,
            "parent_id": 7
        },
        {
            "id": 9,
            "parent_id": 7
        },
        {
            "id": 10,
            "parent_id": 7
        },
        {
            "id": 11,
            "parent_id": 3
        },
        {
            "id": 12,
            "parent_id": 11
        },
        {
            "id": 13,
            "parent_id": 11
        },
        {
            "id": 14,
            "parent_id": 11
        },
        {
            "id": 15,
            "parent_id": 11
        },
        {
            "id": 16,
            "parent_id": 11
        },
        {
            "id": 17,
            "parent_id": 3
        },
        {
            "id": 18,
            "parent_id": 17
        },
        {
            "id": 19,
            "parent_id": 17
        },
        {
            "id": 20,
            "parent_id": 17
        }
    ]
}

dir_data = dict_data["data"]
print(dir_data)

# 找出parent_id为空的当作根节点
root = []


def find_child(array, item):
    # 此处的遍历查找相当于mysql的where条件
    flag = False
    item["data"] = []
    for j in array:
        if j["parent_id"] == item["id"]:
            item["data"].append(j)
            flag = True
            # 如果有的话就继续做为父节点进行查找
            find_child(array, j)
    # 如果没有找到就返回
    if not flag:
        item.pop("data")
        return


for i in dir_data:
    if i["parent_id"] is None:
        # 同时去寻找子节点
        find_child(dir_data, i)
        root.append(i)

print(json.dumps(root))

打印结果为一个多根节点的三级目录结构:

[
    {
        "id": 1,
        "parent_id": null,
        "data": [
            {
                "id": 2,
                "parent_id": 1
            }
        ]
    },
    {
        "id": 3,
        "parent_id": null,
        "data": [
            {
                "id": 4,
                "parent_id": 3,
                "data": [
                    {
                        "id": 5,
                        "parent_id": 4
                    },
                    {
                        "id": 6,
                        "parent_id": 4
                    }
                ]
            },
            {
                "id": 7,
                "parent_id": 3,
                "data": [
                    {
                        "id": 8,
                        "parent_id": 7
                    },
                    {
                        "id": 9,
                        "parent_id": 7
                    },
                    {
                        "id": 10,
                        "parent_id": 7
                    }
                ]
            },
            {
                "id": 11,
                "parent_id": 3,
                "data": [
                    {
                        "id": 12,
                        "parent_id": 11
                    },
                    {
                        "id": 13,
                        "parent_id": 11
                    },
                    {
                        "id": 14,
                        "parent_id": 11
                    },
                    {
                        "id": 15,
                        "parent_id": 11
                    },
                    {
                        "id": 16,
                        "parent_id": 11
                    }
                ]
            },
            {
                "id": 17,
                "parent_id": 3,
                "data": [
                    {
                        "id": 18,
                        "parent_id": 17
                    },
                    {
                        "id": 19,
                        "parent_id": 17
                    },
                    {
                        "id": 20,
                        "parent_id": 17
                    }
                ]
            }
        ]
    }
]

本文地址：https://blog.csdn.net/qq_33036061/article/details/110436957