聊天帖

递归 & 分治

本页面将介绍递归与分治算法的区别与结合运用。

递归

定义

递归（英语：Recursion），在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。

引入

要理解递归，就得先理解什么是递归。

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

以下是一些有助于理解递归的例子：

1. 什么是递归？
2. 如何给一堆数字排序？答：分成两半，先排左半边再排右半边，最后合并就行了，至于怎么排左边和右边，请重新阅读这句话。
3. 你今年几岁？答：去年的岁数加一岁，1999 年我出生。
4. 

递归在数学中非常常见。例如，集合论对自然数的正式定义是：1 是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。

递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。

为什么要写递归

1. 结构清晰，可读性强。例如，分别用不同的方法实现 归并排序：

   C++Python
   

   1 2 3 4 5 6 7 8 9101112131415161718

   // 不使用递归的归并排序算法template <typename T>void merge_sort(vector<T> a) { int n = a.size(); for (int seg = 1; seg < n; seg = seg + seg) for (int start = 0; start < n - seg; start += seg + seg) merge(a, start, start + seg - 1, std::min(start + seg + seg - 1, n - 1));}// 使用递归的归并排序算法template <typename T>void merge_sort(vector<T> a, int front, int end) { if (front >= end) return; int mid = front + (end - front) / 2; merge_sort(a, front, mid); merge_sort(a, mid + 1, end); merge(a, front, mid, end);}

   
   
   
   
   
   
   

   显然，递归版本比非递归版本更易理解。递归版本的做法一目了然：把左半边排序，把右半边排序，最后合并两边。而非递归版本看起来不知所云，充斥着各种难以理解的边界计算细节，特别容易出 bug，且难以调试。

2. 练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时，递归写多了就能敏锐发现这个特点，进而高效解决问题。

分治

定义

分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

过程

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

1. 分解原问题为结构相同的子问题。
2. 分解到某个容易求解的边界之后，进行递归求解。
3. 将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征：

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

注意

如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。此时虽然也可用分治法，但一般用 动态规划 较好。

以归并排序为例。假设实现归并排序的函数名为 merge_sort。明确该函数的职责，即 对传入的一个数组排序。这个问题显然可以分解。给一个数组排序等于给该数组的左右两半分别排序，然后合并成一个数组。

传给它半个数组，那么处理完后这半个数组就已经被排好了。注意到，merge_sort 与二叉树的后序遍历模板极其相似。因为分治算法的套路是 分解 -> 解决（触底）-> 合并（回溯），先左右分解，再处理合并，回溯就是在退栈，即相当于后序遍历。

merge 函数的实现方式与两个有序链表的合并一致。

要点

写递归的要点

明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节， 否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。

以遍历二叉树为例。

这几行代码就足以遍历任何一棵二叉树了。对于递归函数 traverse(root)，只要相信给它一个根节点 root，它就能遍历这棵树。所以只需要把这个节点的左右节点再传给这个函数就行了。

同样扩展到遍历一棵 N 叉树。与二叉树的写法一模一样。不过，对于 N 叉树，显然没有中序遍历。

区别

递归与枚举的区别

递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题；而递归是把问题逐级分解，是纵向的拆分。

递归与分治的区别

递归是一种编程技巧，一种解决问题的思维方式；分治算法很大程度上是基于递归的，解决更具体问题的算法思想。

例题详解

437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过 1000 个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

参考代码

题目解析

习题

• LeetCode 上的递归专题练习
• LeetCode 上的分治算法专项练习

参考资料与注释

1. labuladong 的算法小抄 - 递归详解 ↩

本页面最近更新：2024/5/8 20:33:33，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：AngelKitty, NachtgeistW, abc1763613206, algofighter, Alisahhh, CBW2007, ChungZH, Enter-tainer, flyhahe, fudonglai, Haohu Shen, houbaron, iamtwz, invalid-email-address, Ir1d, Konano, ksyx, labuladong, leoleoasd, Lutra-Fs, melxy1997, Menci, shawlleyw, sshwy, StudyingFather, TrisolarisHD, wongsyrone, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

Copyright © 2016 - 2024 OI Wiki Team

Made with Material for MkDocs

最近更新：2a3a64358, 2024-09-01

动态规划部分简介

本章将介绍介绍动态规划（Dynamic Programming, DP）及其解决的问题、根据其设计的算法及优化。

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。