数据结构与算法（第二季）：尾调用、尾递归、回溯、剪枝
2022-01-17 本文已影响0人
萧1帅
尾调用（Tail Call）
一、概念
- 一个函数的最后一个动作是调用函数。
image
- 如果最后一个动作是调用自身，成为
尾递归，是尾调用的特殊情况。
image
- 很多编译器会对
尾递归函数进行优化，空间复杂度会降低。所以可以将递归优化成尾递归。
image
回溯（Back Tracking）
一、概念
- 回溯可以理解为：通过选择不同的岔路口来通往目的地。
- 每一步都选择一条路触发，能进则进，不能进则退回上一步（
回溯），换一条路再试。 - 树前序遍历和图的深度优先搜索（DFS）就是典型的回溯算法。
image
二、练习
剪枝（Pruning）
image
image
- 即
else中的代码就代表剪枝操作。(什么也不做)
