递归

递归是⼀种优雅的问题解决⽅法，
是一种分⽽治之(divide and conquer，D&C)的⽅法。
递归，就是函数调⽤⾃⼰。

递归的核心思想 就是：把问题分解成规模更小，但和原问题有着相同解法的问题。

编写递归函数时，必须告诉它何时停⽌递归。正因为如此，每个递归函数都有两部分：

• 基线条件（base case）: 函数调⽤⾃⼰的条件
• 递归条件（recursive case）: 函数不再调⽤⾃⼰的条件，从⽽避免形成⽆限循环。

其中有一个基础的编程概念 - 调⽤栈（call stack）。调⽤栈不仅对编程来说很重要，使⽤递归时也必须理解这个概念

示例 - 求阶乘

• 压栈: x==1之前，压了三个函数栈，但一个都没调用结束
• 出栈: x==1后，从栈顶开始出栈

使⽤栈虽然很⽅便，但是也要付出代价：存储详尽的信息可能占⽤⼤量的内存。每个函数调⽤都要占⽤⼀定的内存，如果栈很⾼，就意味着计算机存储了⼤量函数调⽤的信息。在这种情况下，你有两种选择。

• 重新编写代码，转⽽使⽤循环。
• 使⽤尾递归。这是⼀个⾼级递归主题，不在本书的讨论范围内。另外，并⾮所有的语⾔都⽀持尾递归。

练习

• 假设你编写了⼀个递归函数，但不⼩⼼导致它没完没了地运⾏。正如你看到的，对于每次函数
  调⽤，计算机都将为其在栈中分配内存。递归函数没完没了地运⾏时，将给栈带来什么影响？

⼩结

• 递归指的是调⽤⾃⼰的函数。
• 每个递归函数都有两个条件：基线条件和递归条件。
• 栈有两种操作：压⼊和弹出。
• 所有函数调⽤都进⼊调⽤栈。
• 调⽤栈可能很长，这将占⽤⼤量的内存

递归转循环

递归转尾递归

比如维特比算法+

有些简单的递归问题，可以不借助堆栈结构而改成循环的非递归问题。

递归的应用

维特比算法

见 。。

快排

见 。。

RNN、LSTM

递归神经网络（RNN）是两种人工神经网络的总称。一种是时间递归神经网络（recurrent neural network），另一种是结构递归神经网络（recursive neural network）。

扩展阅读

• 为什么说递归效率低？ | 知乎
• 漫谈递归转非递归 | cnblog