递归

递归

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

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

#

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

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

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

示例 - 求阶乘

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

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

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

练习

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

 ⼩结

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

递归转循环

递归转尾递归

比如维特比算法+

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

递归的应用

维特比算法

见 。。

快排

见 。。

RNN、LSTM

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

扩展阅读