递归思想在算法与数据结构中发挥到的作用
程序员文章站
2023-12-29 17:54:46
文章目录递归思想什么情况下使用递归?案例总结1. 求 a = [1, 2, 3, 4, [5, 6, [7, 8]]] 中所有元素的和。2. 求斐波那契数列第n项数值3. n的阶乘问题4. 多级目录树问题，目录的根为多个或者一个，目录的级别从一级到多级。递归思想 递归是在算法求解中比较常见的一种求解思路，通过自身调用，递归能够减少我们在程序中书写很多逻辑代码，在有些场景下，能够实现for和while不能达到的目的。 递归的基本原理是: 每次自身调用时都会在本地栈复制一份作用域出来，存放变量和参数...
文章目录
递归思想
递归是在算法求解中比较常见的一种求解思路，通过自身调用，递归能够减少我们在程序中书写很多逻辑代码，在有些场景下，能够实现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