递归

递归是⼀种优雅的问题解决⽅法，
是一种分⽽治之(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

背景知识

• 栈: 是向低地址扩展的数据结构，是一块连续的内存区域。 栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS 下，栈的大小是 2M （也有的说是 1M ，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示 overflow 。因此，能从栈获得的空间较小。
  • 由系统自动分配，速度较快。但程序员是无法控制的
• 堆：是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
  • 堆是由 new 分配的内存，一般速度比较慢，而且容易产生内存碎片 , 不过用起来最方便 。
• 变量
• 二进制存储，数值在内存中的表示
  -

many languages have “variables”

计算机内存就像是很多盒子的集合体，每个盒子都有地址。
在很多语言中，给变量赋值可以理解成把value放入盒子，比如：

int a = 1;

a = 2;

只是替换了盒子里的内容。

int b = a;

C - 面向过程

1. 运行时，首先系统为整个函数栈预分配空间(一块连续的内存区域)，栈上存储该函数的局部变量。即变量a对应固定的盒子(地址)。
2. 执行 int a = 1 即把数值1放入a对应的盒子
3. 执行 a = 2 替换了a盒子里的内容

C++ - 半面向对象

Java 不完全 面向对象

1. Java中的原始类型 primitive type，与C语言类似，变量对应盒子
   1. 运行 int a = 1，存储在栈中
   2. 运行 a = 2，
2. class，与python类似，变量
   1. 运行 Integer b = 1，存储在栈中还是堆中？貌似有个Integer池，预分配好的。
3. 运行 Integer c = 1000，会new 一个Integer Object，并存储在堆中

疑问

• java不预分配函数栈空间吗？
• java中为什么是frames和objects？为什么不是stack heap？
• java中的原始类型，与class类型

python - 面向对象

python has “names”

1. python中一切皆对象，a=1，a是PyIntObject的对象，存储在堆中
2. python has “names”，指的是python的变量都是代号(盒子中存的是地址，而不是value)。
3. a=2，是把a指向了对象2

疑问

• python中是frame的概念，不是stack。why？

javascript

扩展阅读

• code like a pythonista: idiomatic python
• http://pythontutor.com