本文已收录到 GitHub · AndroidFamily，有 Android 进阶常识体系，欢送 Star。技术和职场问题，请关注公众号 [彭旭锐] 进 Android 面试交换群。
前言
大家好，我是小彭。
明天分享到计算机科学中一个根底又十分重要的概念 —— 递归。递归是计算机中特有的概念，你很难在事实世界中找到一个失当的例子与之关联起来。因而，对于很多初学编程的人，一开始会很难了解。
那么，到底什么是递归，咱们为什么要应用递归？咱们明天就围绕这两个问题开展。
学习路线图：
1. 什么是递归？
递归（Recursion）是一种通过“函数本人调用本人”的形式，将问题反复地合成为同类子问题，并最终解决问题的编程技巧。
举个例子，要求一个数 $n$ 的阶乘 $n! = n*(n-1)*(n-2)*…*2*1$，有 2 种思考问题的思路：
- 递推（个别思维）： 咱们从 $1$ 开始，用 $1$ 乘以 $2$ 失去 $2!$ 问题的解，用 $3$ 乘以 $2!$ 失去 $3!$ 问题的解。顺次类推，直到用 $n$ 乘以 $(n-1)!$ 失去原问题 $n!$ 的解。这就是用递推解决问题，这是绝对简略间接的思考形式；
- 递归（计算机思维）： 咱们把 $n!$ 的问题拆分为一个 $(n-1)!$ 的问题，如果咱们晓得 $(n-1)!$ 的解，那么将它乘以 $n$ 就能够得出 $n!$ 的解。以此类推，咱们将一个 $(n-1)!$ 的问题拆分为同类型的规模更小的 $(n-2)!$ 子问题，直到拆分到无奈拆分，能够间接得出后果 $1!$ 问题。此时，咱们再沿着拆分问题的门路，反向地依据子问题的解求出原问题的解，最终失去原问题 $n!$ 的后果。这就是用递归解决问题。
求 n!
从这个例子能够看出， 递归其实是在反复地做 2 件事：
- 1、自顶向下拆分问题： 从一个很难间接求出后果的、规模较大的原问题开始，逐步向下拆分为规模较小的子问题（从 $n!$ 拆分到 $(n-1)!$），直到拆分到问题边界时进行拆分，这个拆分的过程就是“递”（问题边界也叫基准状况或终止条件）；
- 2、自底向上组合后果： 从问题边界开始，逐步向上传递并组合子问题的解（从 $(n-1)!$ 失去 $n!$），直到最终回到原问题取得后果，这个组合的过程就是“归”。
看到这里你会不会产生一个疑难： 咱们间接从问题边界 $1!$ 一层层自底向上组合后果也能够失去 $n!$ 的解，自顶向下拆分问题的过程显得没有必要。的确，对于对于这种原问题与子问题只是 “线性” 地缩小一个问题规模的状况，的确是这样。然而对于很多略微简单一些的问题，原问题与子问题会形成一个树型的 “非线性” 构造，这个时候就适宜用递归解决，很难用递推解决。
举个例子， 求斐波那契数列，这个问题同时也是 LeetCode 上的一道典型例题：LeetCode · 509. 斐波那契数：该数列从 $1$ 开始，每一项数字都是后面两项数字的和。
LeetCode 例题
尽管，咱们能够利用递推的形式从 $F(0)$ 和 $F(1)$ 自底向上推导出 $F(n)$ 的解，然而这种非线性的形式在编程语言中很难实现，而应用递归的形式自顶向下地解决问题，在编码上是很容易实现的。
当然，这段代码中存在十分多的反复计算，最终使得整个算法的工夫复杂度达到惊人的指数级 $O(2^n)$。例如在计算 $F(5)=F(3)+F(4)$ 和 $F(6)=F(4)+F(5)$ 的时候，$F(4)$ 就被反复计算 2 次，这种反复计算完全相同的子问题的状况就叫 重叠子问题 ，当前咱们再专门探讨。
用递归解决斐波那契数列
用递归解决（无优化）
class Solution {fun fib(N: Int): Int {if(N == 0){return 0}
if(N == 1){return 1}
// 拆分问题 + 组合后果
return fib(N - 1) + fib(N - 2)
}
}2. 递归的解题模板
- 1、判断以后状态是否异样，例如数组越界，
n < 0等； - 2、判断以后状态是否满足终止条件，即达到问题边界，能够间接求出后果；
- 3、递归地拆分问题，放大问题规模；
- 4、组合子问题的解，联合以后状态得出最终解。
fun func(n){
// 1. 判断是否处于异样条件
if(/* 异样条件 */){return}
// 2. 判断是否满足终止条件（问题边界）if(/* 终止条件 */){return result}
// 3. 拆分问题
result1 = func(n1)
result2 = func(n2)
...
// 4. 组合后果
return combine(result1, result2, ...)
}3. 计算机如何实现递归？
递归程序在解决子问题之后，须要沿着拆分问题的门路一层层地原路返回后果，并且后拆分的子问题应该先解决。这个逻辑与栈“后进先出”的逻辑齐全吻合：
- 拆分问题： 就是一次子问题入栈的过程；
- 组合后果： 就是一次子问题出栈的过程。
事实上，这种出栈和入栈的逻辑，在编程语言中是人造反对的，不须要程序员实现。程序员只须要保护拆分问题和组合问题的逻辑，一次函数自调用和返回的过程就是一次隐式的函数出栈入栈过程。在程序运行时，内存空间中会存在一块保护函数调用的区域，称为 函数调用栈 ，函数的调用与返回过程，就人造对应着一次子问题入栈和出栈的过程：
- 调用函数： 程序会创立一个新的栈帧并压入调用栈的顶部；
- 函数返回： 程序会将以后栈帧从调用栈栈顶弹出，并带着返回值回到上一层栈帧中调用函数的地位。
咱们在剖析递归算法的空间复杂度时，也必须将隐式的函数调用栈思考在内。
4. 递归与迭代的区别
递归（Recursion）和迭代（Iteration）都是编程语言中反复执行某一段逻辑的语法。
语法上的区别在于：
- 迭代： 通过迭代器（for/while）反复执行某一段逻辑；
- 递归： 通过函数自调用反复执行函数中的一段逻辑。
外围区别在于解决问题的思路不同：
- 迭代：迭代的思路认为只有从问题边界开始，在所有元素上反复执行雷同的逻辑，就能够取得最终问题的解（迭代的思路与递推的思路相似）；
- 递归：递归的思路认为只有将原问题拆分为子问题，在每个子问题上反复执行雷同的逻辑，最终组合所有子问题的后果就能够取得最终问题的解。
例如，在计算 n! 的问题中，递推或迭代的思路是从 1! 开始反复乘以更大的数，最终取得原问题 n! 的解；而递归的思路是将 n! 问题拆分为 (n-1)! 的问题，最终通过 (n-1)! 问题取得原问题 n! 的解。
再举个例子，面试中呈现频率十分高的反转链表问题，同时也是 LeetCode 上的一道典型例题：LeetCode 206 · 反转链表。假如链表为 1 → 2 → 3 → 4 → ∅，咱们想要把链表反转为 ∅ ← 1 ← 2 ←3 ←4，用迭代和递归的思路是不同的：
- 迭代： 迭代的思路认为，只有反复地在每个节点上解决同一个逻辑，最终就能够失去反转链表，这个逻辑是：“将以后节点的 next 指针指向前一个节点，再将游标指针挪动到后一个节点”。
- 递归： 递归的思路认为，只有将反转链表的问题拆分为“让以后节点的 next 指针指向前面整段子链的反转链表”，在每个子链表上反复执行雷同的逻辑，最终就可能取得整个链表反转的后果。
这两个思路用示意图示意如下：
示意图
迭代题解
class Solution {fun reverseList(head: ListNode?): ListNode? {
var cur: ListNode? = head
var prev: ListNode? = null
while (null != cur) {
val tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
}
return prev
}
}迭代解法复杂度剖析：
- 工夫复杂度：每个节点扫描一次，工夫复杂度为 $O(n)$；
- 空间复杂度：应用了常量级别变量，空间复杂度为 $O(1)$。
递归题解
class Solution {fun reverseList(head: ListNode?): ListNode? {if(null == head || null == head.next){return head}
val newHead = reverseList(head.next)
head.next.next = head
head.next = null
return newHead
}
}递归解法复杂度剖析：
- 工夫复杂度：每个节点扫描一次，工夫复杂度为 $O(n)$；
- 空间复杂度：应用了函数调用栈，空间复杂度为 $O(n)$。
实践上认为迭代程序的运行效率会比递归程序更好，并且任何递归程序（不止是尾递归，尾递归只是打消起来绝对容易）都能够通过一个栈转化为迭代程序。然而，这种打消递归的做法实际上是以就义程序可读性为代价换取的，个别不会为了运行效率而刻意打消递归。
不过，有一种非凡的递归能够被轻松地打消，一些编译器或运行时会主动实现打消工作，不须要程序员手动打消，也不会毁坏代码的可读性。
5. 尾递归
在编程语言中，尾调用是指在一个函数的最初返回另一个函数的调用后果。如果尾调用最初调用的是以后函数自身，就是尾递归。为什么咱们要专门定义这种非凡的递归模式呢？因为尾递归也是尾调用，而在大多数编程语言中，尾调用能够被轻松地打消，这使得程序能够模仿递归的逻辑而又不损失性能，这叫 尾递归优化 / 尾递归打消 。例如，以下 2 段代码实现的性能是雷同的，前者是尾递归，而后者是迭代。
尾递归
fun printList(itr : Iterator<*>){if(!itr.hasNext()) {return}
println(itr.next())
// 尾递归
printList(itr)
} 迭代
fun printList(itr : Iterator<*>){while(true) {if(!itr.hasNext()) {return}
println(itr.next())
}
} 能够看到，应用一个 while 循环和若干变量打消就能够轻松打消尾递归。
6. 总结
到这里，置信你曾经对递归的含意以及递归的弱小之处有所理解。 递归是计算机科学中特有的解决问题的思路：先通过自顶向下拆分问题，再自底向上组合后果来解决问题。这个思路在编程语言中能够用函数自调用和返回实现，因而递归在编程实现中会显得十分简洁。 正如图灵奖获得者尼克劳斯·维尔特所说：“递归的弱小之处在于它容许用户用无限的语句形容有限的对象。因而，在计算机科学中，递归能够被用来形容有限步的运算，只管形容运算的程序是无限的。”
另外，你会发现“先拆分问题再合并后果”的思维与“分治思维”雷同，那么你认为递归和分治是等价的吗？这个咱们下回说。
发现一个 Google 的小彩蛋：在 Google 搜寻里搜寻“递归”，提醒词里会显示“您是不是要找：递归”。这就会产生递归的成果的，因为点击提醒词“递归”后，还是会递归地显示“您是不是要找：递归”。哈哈，应该是 Google 跟程序员开的小玩笑。
参考资料
- 数据结构与算法剖析 · Java 语言形容（第 1 章 · 引论、第 3 章 · 表栈和队列、第 10 章 · 算法设计技巧）—— [美] Mark Allen Weiss 著
- 算法导论（第 4 章 · 分治策略）—— [美] Thomas H. Cormen 等 著
- 算法吧 · 递归 —— liweiwei1419 著
- Recursion (computer science)) —— Wikipedia
- Divide-and-conquer algorithm —— Wikipedia
- Iterator —— Wikipedia
- Tail call —— Wikipedia