谷歌递归算法视频教程

1. Google:有100阶楼梯，从底往上爬，每次爬1阶或2阶，编算法说明共有多少走法

设 f(x) = 上x层楼的方法数，那么，显然

f(1) = 1
f(2) = 2

因为只有1层楼的话，只有一种方法可以走完，那就是直接走一阶；
只有2层楼的话，可以走两步一阶，或者走一步2阶，共两种走法；

考虑一般的 x (x >= 3)：
假如你现在面对 x 层楼梯，你只有两种选择：

1. 要么走一阶，变成还剩 x-1 层，这种情况下剩下的楼层共有 f(x-1) 种走法。
2. 要么走两阶，变成 x-2 层，这种情况下剩下的楼层共有 f(x-2) 种走法。

所以对于一般的 x 层楼梯，你实际上有 f(x-1) + f(x-2) 种走法。

于是就得到了一个递推公式：

f(1) = 1
f(2) = 2
f(x) = f(x-1) + f(x-2) (x >= 3)

2. 什么是递归递归有什么用

1、程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

2、递归一般的作用用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。
(3)数据的结构形式是按递归定义的。

3. 计算机里面什么是递归

在数学和计算机科学中，当一类对象或方法可以由两个属性定义时，它们表现出递归行为:

简单的基线条件---不使用递归产生答案的终止情况

一组规则将所有其他情形缩减到基线条件

例如，以下是某人祖先的递归定义:

某人的父母是他的祖先(基线条件)

某人祖先的祖先也是他的祖先(递归步骤)

斐波那契数列是递归的经典例子:

Fib(0) = 1 基线条件1；

Fib(1) = 1 基线条件2；

对所有整数n,n > 1时：Fib(n) = (Fib(n-1) + Fib(n-2))。

许多数学公理基于递归规则。例如，皮亚诺公理对自然数的形式定义可以描述为:0是自然数，每个自然数都有一个后继数，它也是自然数。通过这种基线条件和递归规则，可以生成所有自然数的集合。

递归定义的数学对象包括函数、集合，尤其是分形。

递归还有多种开玩笑的“定义”。

非正式定义

俄罗斯娃娃或俄罗斯套娃是递归概念的一个物理艺术例子。

自1320年乔托的Stefaneschi三联画问世以来，递归就一直用于绘画。它的中央面板包含红衣主教Stefaneschi的跪像，举着三联画本身作为祭品。

M.C. Eschers 印刷画廊 (1956)描绘了一个扭曲的城市，其中包含一个递归包含图片的画廊，因此无限。

4. Google 实时流拥塞控制算法GCC

1、简介

参考：https://tools.ietf.org/html/draft-ietf-rmcat-gcc-02#section-4.4

gcc是google实时流拥塞控制算法的简称，已经在webrtc中实现，应用于chrome，后面将应用到Hangouts（视频聊天产品）中，主要用于视频流的拥塞控制。

网络瓶颈主要发生在中间的传输设备上，比如路由器，所以如果有中间设备的帮助（ECN），网络瓶颈应该会更早并且更准确的被检测到，gcc属于端到端的拥塞控制算法，端到端的算法将中间路径想象成一个黑盒子，它不借助中间设备的帮助，这就增加了网络拥塞预测的难度。端到端的实时流拥塞算法主要有以下难点：

（1）网络拥塞一般与链路容量，当前链路中的流量以及即将发送的流量有关，由于路由的不确定性以及链路是由多个流共享并且瞬息万变等原因，对于一个流而言这三个因素都是随机变量。

（2）拥塞控制算法要求同一种流（都使用gcc）能够公平分享带宽，同时能够与TCP流公平相处，不会被TCP流抢占带宽，也尽量不要抢占TCP流的带宽。

（3）视频解码器对丢包敏感，但实时性又不能使用重传机制，因为需要尽量减少丢包，另一方面解码器并不能快速的调整码率，因而估计出的带宽尽量平滑，减少毛刺。

2、实现

gcc由基于延迟的控制器和基于丢包的控制器组成，信令基于RTP扩展头和RTCP传输。

（1）反馈和扩展

gcc可以有两种实现，第一种是两种控制器都在发送端实现，接收端周期性的反馈到达的每一个包的序列号和到达时间，发送端记录每一个包的发送时间和到达时间，同时计算出丢包率。第二种是延迟控制器在接收端实现，接收端计算出组间延迟，根据组间延迟计算出发送比特率通过REMB消息反馈给发送端，接收端通过RTCP消息将丢包率反馈给发送端，丢包控制器在发送端实现，发送端通过接收端反馈的信息计算出最终的发送比特率。

（2）发送引擎

定速器用于实现发送固定比特率的视频包，编码器产生的数据先会放到定时队列中，定时器会在每个burst_time发送一组包，burst_time建议为5ms，这一组包的大小是由发送比特率和burst_time计算出来的。

（3）延迟控制器

（3.1）到达时间模型

d(i) = t(i) - t(i-1) - (T(i) - T(i-1)) 

d(i)表示第i组包的延迟和第i-1组包的延迟之差，t(i)表示第i组包的到达时间，取最后一个包的到达时间，T(i)表示第i组包的发送时间，取最后一个包的发送时间，忽略乱序的包。

d(i) > 0说明组间的延迟增大了，d(i) < 0说明组间的延迟减少了，d(i) = 0说明组间的延迟没变化。

我们将组间延迟建模成 d(i) = w(i)，w(i)是一个随机过程W的采样，这个随机过程是链路容量，当前链路的流量以及当前发送的比特率的函数。将W建模成白高斯过程。如果我们过度使用链路则我们期望w(i)增大，如果链路中的队列正在排空，则意味着w(i)将会减小，其它情况w(i)将是0。

d(i) = w(i) = m(i) + v(i)

m(i)是从w(i)中提取出来的使w(i)的均值为0的部分。v(i)是噪声项代表网络抖动以及其它模型捕捉不到的影响延迟的因素，v(i)是均值为0的高斯白噪声，方差var_v = E{v(i)^2}。

（3.2）滤波之前

链路中断会使延迟瞬间变化很大，影响模型的准确计算，所以滤波之前会把一些包合并成一组，如果满足下面的条件将会合并，（1）一些包的发送时间在一个burst_time内（2）一个包的组间到达时间小于burst_time并且组间延迟d(i)小于0。

（3.3）到达时间滤波

我们将要估计m(i)然后用这个估计值检测链路过载。gcc使用kalman滤波器来估计m(i)。

m(i+1) = m(i) + u(i)

上面的是m(i)的状态转移方程。u(i)是状态噪声，将它建模成均值为0，方差为q(i)的符合高斯统计的稳态过程，其中q(i) = E{u(i)^2}，q(i)建议值为10^-3。

kalman滤波器递归地更新m(i)的估计值m_hat(i)

z(i) = d(i) - m_hat(i-1)

m_hat(i) = m_hat(i-1) + z(i) * k(i)

 k(i) = (e(i-1) + q(i)) / var_v_hat(i) + (e(i-1) + q(i))

e(i) = (1 - k(i)) * (e(i-1) + q(i))

其中；

var_v_hat(i) = max(alpha * var_v_hat(i-1) + (1-alpha) * z(i)^2, 1)

alpha = (1-chi)^(30/(1000 * f_max))

f_max = max {1/(T(j) - T(j-1))} for j in i-K+1,...,i 代表最近K组包的最大发送频率。

（3.4）过载探测

用到达时间滤波模块估计出的组间延迟m(i)与阈值del_var_th(i)进行比较，如果m(i) > del_var_th(i)则意味着过载，这一个条件还不能给速率控制系统发送过载信号，检测的过载时间最少维持overuse_time_th毫秒，并且不能出现m(i) < m(i-1)的情况。相反的情况，如果m(i) < -del_var_th(i)则意味着网络使用不足，最后一种情况是正常状态。

del_var_th对算法的整体仿真和性能有很大的影响，另外如果del_var_th取一个固定的值，将会被当前的TCP流占用带宽导致饥饿的产生。这个饥饿可以通过将del_var_th设置成足够大的值而避免。因而有必要动态调整del_var_th去获取更好的性能，例如与基于丢包的流的竞争中。

del_var_th(i) = del_var_th(i-1) + (t(i)-t(i-1)) * K(i) * (|m(i)|-del_var_th(i-1))

另外，如果|m(i)| - del_var_th(i) > 15时不更新del_var_th(i)，并且del_var_th(i) 在[6, 600]区间内。

（3.5）速率控制器

当检测到过载，延迟控制器估计的有效带宽将会减少，通过这种方式获得一个递归的自适应的有效带宽估计。

速率控制子系统有3个状态，Increase, Decrease 和Hold状态。当没有检测出拥塞时是Increase状态，检测出拥塞时是Decrease状态，Hold状态表示等待队列清空的过程。

增大当前有效带宽将使用乘法或加法，取决于当前的状态，如果当前估计的带宽离拥塞较远，则使用乘法，如果接近拥塞，则使用加法。如果当前的比特率R_hat(i)接近之前Decrease状态的平均比特率则认为接近拥塞。

R_hat(i)是延迟控制器在T秒钟的窗口中计算出来的接收比特率：

R_hat(i) = 1/T * sum(L(j)) for j from 1 to N(i)

其中N(i)是T秒钟接收的包数，L(j)是第j个包的负载长度。窗口建议设置成0.5秒到1秒之间。

eta = 1.08^min(time_since_last_update_ms / 1000, 1.0)

A_hat(i) = eta * A_hat(i-1)

在加法增长阶段，估计值在response_time最多增长半个包的长度。

response_time_ms = 100 + rtt_ms

alpha = 0.5 * min(time_since_last_update_ms / response_time_ms, 1.0)

A_hat(i) = A_hat(i-1) + max(1000, alpha * expected_packet_size_bits)

expected_packet_size_bits用于在低码率时获得一个缓慢的增长。它可以根据当前的码率估算出来。

bits_per_frame = A_hat(i-1) / 30

packets_per_frame = ceil(bits_per_frame / (1200 * 8))

avg_packet_size_bits = bits_per_frame / packets_per_frame

之前的讨论都是假设链路会出现拥塞，如果发送端产生不了足够的比特流，估计的有效带宽需要保持在一个给定的范围内。

A_hat(i) < 1.5 * R_hat(i)

如果检测到过载，则进入Decrease状态，延迟控制器估计的有效带宽会减少。

A_hat(i) = beta * R_hat(i)

beta一般选择属于[0.8, 0.95]，一般建议是0.85。

（4）丢包控制器

定义丢包控制器估计有效带宽为As_hat。

延迟控制器估计的有效带宽只在队列足够大时有效，如果队列较小，就需要使用丢包率检测过载。

As_hat(i) = As_hat(i - 1)      （2 < p < 10%）

As_hat(i) = As_hat(i-1)(1-0.5p） （p > 10%）

As_hat(i) = 1.05(As_hat(i-1))      (p < 2%)

真实的发送速率设置成丢包控制器估计值和延迟控制器估计值的较小的。

我们观察到由于过载出现少量的丢包，如果不调整发送的比特率，丢包率会快速增长到达10%门限值然后调整发送比特率。然而，如果丢包率不增加，拥塞很可能不是自己造成的，因而不需要进行调整。

（5）互操作

如果发送端实现了这个算法，但是接收端没有实现RTCP消息和RTP头扩展，建议发送端检测RTCP的接收端报告，然后使用丢包率和rtt做为丢包控制器的输入，关闭延迟控制器。

注：服务中的自适应流控也可以参考GCC，后面这个是BRPC的流控： BRPC自适应流控

5. 15个变态的谷歌面试问题的答案

十二题可是初三上学期的物理题啊,关于天平的!
答案是:把八个硬币其中3个放左盘,在选另外3个放右盘,其余两个先不管,如果两个盘一样重,则重的硬币在剩下的两个硬币中,在称这两个硬币,ok.若其中一个盘较重,就把这个盘的三个硬币,其中一个放左盘,另一个放右盘再测,如果相等,则重的是剩下的1个硬币,如果天平不平衡,则重的硬币在较重的盘上.
第五题则是关于数学几何图形,大概是初二初三接触过的,要知道井盖在路上,肯定是有东西在井盖的边缘托住他,井盖才不会掉下去,而这个边缘是很小的.那么井盖是圆的话,半径相等,如果井盖因某种原因而打侧放的话由于直径比边缘要长,不至于令井盖掉下去.如果井盖是矩形的话,一打侧他就会掉下去了,因为矩形由两个直角三角形组成,而直角三角形的斜边较长.如果照这样说等边三角形也应该可以啊,一些不规则图形也可以,可能也有美观这一因素在吧,又或者是井盖作者先想到圆井盖,后来全世界都圆井盖了,就没人在意去计较为什么不用等边三角形井盖了...由于所学知识有限,当时我问老师为什么不能用等边三角形,老师没答我.不能给你证明,抱歉.
第七题,首先思考一下,每一秒分针时针都在转动,那么在重合的时候的下一秒,时针分针会不会再重合一次?想深一层,我觉得应从圆的度数方面考虑,通过计算得知,分针每走一小格(一分钟),走了6度,而时针走了0.5度.那么,假如现在是十二点,时针分针都指在了"12"上,这时重合了一次,但每走一秒,分针都有微妙的转动,而时针也是,那么一秒分针转动了6/60=0.1度,时针转动了0.5/60=0.008333度,即是说,在重合时的下一秒,分针就已经超越了时针,所以一小时只重合一次!(个人认为,本人仅是初三学生,这可能不是正确答案).我觉得,一天24小时,自然是24次.
第十一题属于推理题目,我不知道(呵呵),不过在网上有类似这道题的:海盗分金币,有五个海盗,一号首先开始分金币,如果他的分配方法得不到半数的同意就处死并让下一位去分,这题已有详细答案(很久前就看过了),答案是:逆向思维。
假设每一个海盗都是绝顶聪明而理性，他们都能够进行严密的逻辑推理，并能很理智的判断自身的得失，即能够在保住性命的前提下得到最多的金币。同时还假设每一轮表决后的结果都能顺利得到执行，那么抽到1号的海盗应该提出怎样的分配方案才能使自己既不被扔进海里，又可以得到更多的金币呢？
此题公认的标准答案是：1号海盗分给3号1枚金币，4号或5号2枚金币，自己则独得97枚金币，即分配方案为（97，0，1，2，0）或（97，0，1，0，2）。现来看如下各人的理性分析：
首先从5号海盗开始，因为他是最安全的，没有被扔下大海的风险，因此他的策略也最为简单，即最好前面的人全都死光光，那么他就可以独得这100枚金币了。
接下来看4号，他的生存机会完全取决于前面还有人存活着，因为如果1号到3号的海盗全都喂了鲨鱼，那么在只剩4号与5号的情况下，不管4号提出怎样的分配方案，5号一定都会投反对票来让4号去喂鲨鱼，以独吞全部的金币。哪怕4号为了保命而讨好5号，提出（0，100）这样的方案让5号独占金币，但是5号还有可能觉得留着4号有危险，而投票反对以让其喂鲨鱼。因此理性的4号是不应该冒这样的风险，把存活的希望寄托在5号的随机选择上的，他惟有支持3号才能绝对保证自身的性命。
再来看3号，他经过上述的逻辑推理之后，就会提出（100，0，0）这样的分配方案，因为他知道4号哪怕一无所获，也还是会无条件的支持他而投赞成票的，那么再加上自己的1票就可以使他稳获这100金币了。
但是，2号也经过推理得知了3号的分配方案，那么他就会提出（98，0，1，1）的方案。因为这个方案相对于3号的分配方案，4号和5号至少可以获得1枚金币，理性的4号和5号自然会觉得此方案对他们来说更有利而支持2号，不希望2号出局而由3号来进行分配。这样，2号就可以屁颠屁颠的拿走98枚金币了。
不幸的是，1号海盗更不是省油的灯，经过一番推理之后也洞悉了2号的分配方案。他将采取的策略是放弃2号，而给3号1枚金币，同时给4号或5号2枚金币，即提出（97，0，1，2，0）或（97，0，1，0，2）的分配方案。由于1号的分配方案对于3号与4号或5号来说，相比2号的方案可以获得更多的利益，那么他们将会投票支持1号，再加上1号自身的1票，97枚金币就可轻松落入1号的腰包了 .但是google的这道题无明确条件,只说如果得不到同意就死,没其他的了,如果船员不管三七二十一全让你死,那你怎么办?或许这题不应用逻辑分析,而是从社会现实角度,例如巴结好熟人之类的呵呵~~
第十题好像在某本书上看过,不过没有写答案,我是这样想的,既然要让他不知道号码,就不能够在纸上写,那么就只能够用手机确认了:让鲍伯拨打我的手机号码.
第十五题,我想出的答案有很多,这种脑筋急转弯式的题在大家眼中有无数答案,但出题人只看他手中的正确答案,所以我把我最雷的一个给你参考吧:如果只有硬币这么小,从平面看搅拌器一般成接近四边形五边形的形状,搅拌刀片转动时是圆,吗么就直接站在搅拌刀片切不到你的死角位置不就ok了?
第三题,生物学解释,生男生女比例1比1,因为概率问题只是大概估算,并无准确答案,考方只想看你的解题思路罢了,我是这样解的:既然是一比1,那么就是要么先生男,要么先生女,由于是大概估算,那么看作每生两次就有一男一女(现实是不可能),即是:先生男的话就不再生,如果生女的话就会在生一个男,把他认作只有这两种情况,且概率都是一比一,就是说两男一女,所以比例就是二比一.
第八题,我不会,不过网上有网友的见解:对于一个软件工程师来说，是要尽量避免在软件中“死牛肉”出现。它不但对软件本身没有好处，还会给整个软件带来破坏。死牛肉不但不能吃还会引来许多仓蝇之类的害虫。
其他题大多属于主观题,没绝对答案,出题人只想看你的思路.不过我已经把能说的都给你说了,只看答案没有用关键是分析,希望我用了1小时的长篇大论对你有帮助

参考资料： 网络大神,老师的谆谆教导

6. 如何用PyTorch实现递归神经网络

从 Siri 到谷歌翻译，深度神经网络已经在机器理解自然语言方面取得了巨大突破。这些模型大多数将语言视为单调的单词或字符序列，并使用一种称为循环神经网络（recurrent neural network/RNN）的模型来处理该序列。但是许多语言学家认为语言最好被理解为具有树形结构的层次化词组，一种被称为递归神经网络（recursive neural network）的深度学习模型考虑到了这种结构，这方面已经有大量的研究。虽然这些模型非常难以实现且效率很低，但是一个全新的深度学习框架 PyTorch 能使它们和其它复杂的自然语言处理模型变得更加容易。

虽然递归神经网络很好地显示了 PyTorch 的灵活性，但它也广泛支持其它的各种深度学习框架，特别的是，它能够对计算机视觉（computer vision）计算提供强大的支撑。PyTorch 是 Facebook AI Research 和其它几个实验室的开发人员的成果，该框架结合了 Torch7 高效灵活的 GPU 加速后端库与直观的 Python 前端，它的特点是快速成形、代码可读和支持最广泛的深度学习模型。

开始 SPINN

链接中的文章（https://github.com/jekbradbury/examples/tree/spinn/snli）详细介绍了一个递归神经网络的 PyTorch 实现，它具有一个循环跟踪器（recurrent tracker）和 TreeLSTM 节点，也称为 SPINN——SPINN 是深度学习模型用于自然语言处理的一个例子，它很难通过许多流行的框架构建。这里的模型实现部分运用了批处理（batch），所以它可以利用 GPU 加速，使得运行速度明显快于不使用批处理的版本。

SPINN 的意思是堆栈增强的解析器-解释器神经网络（Stack-augmented Parser-Interpreter Neural Network），由 Bowman 等人于 2016 年作为解决自然语言推理任务的一种方法引入，该论文中使用了斯坦福大学的 SNLI 数据集。

该任务是将语句对分为三类：假设语句 1 是一幅看不见的图像的准确标题，那么语句 2（a）肯定（b）可能还是（c）绝对不是一个准确的标题？（这些类分别被称为蕴含（entailment）、中立（neutral）和矛盾（contradiction））。例如，假设一句话是“两只狗正跑过一片场地”，蕴含可能会使这个语句对变成“户外的动物”，中立可能会使这个语句对变成“一些小狗正在跑并试图抓住一根棍子”，矛盾能会使这个语句对变成“宠物正坐在沙发上”。

特别地，研究 SPINN 的初始目标是在确定语句的关系之前将每个句子编码（encoding）成固定长度的向量表示（也有其它方式，例如注意模型（attention model）中将每个句子的每个部分用一种柔焦（soft focus）的方法相互比较）。

数据集是用句法解析树（syntactic parse tree）方法由机器生成的，句法解析树将每个句子中的单词分组成具有独立意义的短语和子句，每个短语由两个词或子短语组成。许多语言学家认为，人类通过如上面所说的树的分层方式来组合词意并理解语言，所以用相同的方式尝试构建一个神经网络是值得的。下面的例子是数据集中的一个句子，其解析树由嵌套括号表示：

( ( The church ) ( ( has ( cracks ( in ( the ceiling ) ) ) ) . ) )

这个句子进行编码的一种方式是使用含有解析树的神经网络构建一个神经网络层 Rece，这个神经网络层能够组合词语对（用词嵌入（word embedding）表示，如 GloVe）、 和/或短语，然后递归地应用此层（函数），将最后一个 Rece 产生的结果作为句子的编码：

X = Rece(“the”, “ceiling”)
Y = Rece(“in”, X)
... etc.

但是，如果我希望网络以更类似人类的方式工作，从左到右阅读并保留句子的语境，同时仍然使用解析树组合短语？或者，如果我想训练一个网络来构建自己的解析树，让解析树根据它看到的单词读取句子？这是一个同样的但方式略有不同的解析树的写法：

The church ) has cracks in the ceiling ) ) ) ) . ) )

或者用第 3 种方式表示，如下：

WORDS: The church has cracks in the ceiling .
PARSES: S S R S S S S S R R R R S R R

我所做的只是删除开括号，然后用“S”标记“shift”，并用“R”替换闭括号用于“rece”。但是现在可以从左到右读取信息作为一组指令来操作一个堆栈（stack）和一个类似堆栈的缓冲区（buffer），能得到与上述递归方法完全相同的结果：

1. 将单词放入缓冲区。
2. 从缓冲区的前部弹出“The”，将其推送（push）到堆栈上层，紧接着是“church”。
3. 弹出前 2 个堆栈值，应用于 Rece，然后将结果推送回堆栈。
4. 从缓冲区弹出“has”，然后推送到堆栈，然后是“cracks”，然后是“in”，然后是“the”，然后是“ceiling”。
5. 重复四次：弹出 2 个堆栈值，应用于 Rece，然后推送结果。
6. 从缓冲区弹出“.”，然后推送到堆栈上层。
7. 重复两次：弹出 2 个堆栈值，应用于 Rece，然后推送结果。
8. 弹出剩余的堆栈值，并将其作为句子编码返回。

我还想保留句子的语境，以便在对句子的后半部分应用 Rece 层时考虑系统已经读取的句子部分的信息。所以我将用一个三参数函数替换双参数的 Rece 函数，该函数的输入值为一个左子句、一个右子句和当前句的上下文状态。该状态由神经网络的第二层（称为循环跟踪器（Tracker）的单元）创建。Tracker 在给定当前句子上下文状态、缓冲区中的顶部条目 b 和堆栈中前两个条目 s1\s2 时，在堆栈操作的每个步骤（即，读取每个单词或闭括号）后生成一个新状态：

context[t+1] = Tracker(context[t], b, s1, s2)

容易设想用你最喜欢的编程语言来编写代码做这些事情。对于要处理的每个句子，它将从缓冲区加载下一个单词，运行跟踪器，检查是否将单词推送入堆栈或执行 Rece 函数，执行该操作；然后重复，直到对整个句子完成处理。通过对单个句子的应用，该过程构成了一个大而复杂的深度神经网络，通过堆栈操作的方式一遍又一遍地应用它的两个可训练层。但是，如果你熟悉 TensorFlow 或 Theano 等传统的深度学习框架，就知道它们很难实现这样的动态过程。你值得花点时间回顾一下，探索为什么 PyTorch 能有所不同。

图论

图 1：一个函数的图结构表示

深度神经网络本质上是有大量参数的复杂函数。深度学习的目的是通过计算以损失函数（loss）度量的偏导数（梯度）来优化这些参数。如果函数表示为计算图结构（图 1），则向后遍历该图可实现这些梯度的计算，而无需冗余工作。每个现代深度学习框架都是基于此反向传播（backpropagation）的概念，因此每个框架都需要一个表示计算图的方式。

在许多流行的框架中，包括 TensorFlow、Theano 和 Keras 以及 Torch7 的 nngraph 库，计算图是一个提前构建的静态对象。该图是用像数学表达式的代码定义的，但其变量实际上是尚未保存任何数值的占位符（placeholder）。图中的占位符变量被编译进函数，然后可以在训练集的批处理上重复运行该函数来产生输出和梯度值。

这种静态计算图（static computation graph）方法对于固定结构的卷积神经网络效果很好。但是在许多其它应用中，有用的做法是令神经网络的图结构根据数据而有所不同。在自然语言处理中，研究人员通常希望通过每个时间步骤中输入的单词来展开（确定）循环神经网络。上述 SPINN 模型中的堆栈操作很大程度上依赖于控制流程（如 for 和 if 语句）来定义特定句子的计算图结构。在更复杂的情况下，你可能需要构建结构依赖于模型自身的子网络输出的模型。

这些想法中的一些（虽然不是全部）可以被生搬硬套到静态图系统中，但几乎总是以降低透明度和增加代码的困惑度为代价。该框架必须在其计算图中添加特殊的节点，这些节点代表如循环和条件的编程原语（programming primitive），而用户必须学习和使用这些节点，而不仅仅是编程代码语言中的 for 和 if 语句。这是因为程序员使用的任何控制流程语句将仅运行一次，当构建图时程序员需要硬编码（hard coding）单个计算路径。

例如，通过词向量（从初始状态 h0 开始）运行循环神经网络单元（rnn_unit）需要 TensorFlow 中的特殊控制流节点 tf.while_loop。需要一个额外的特殊节点来获取运行时的词长度，因为在运行代码时它只是一个占位符。

# TensorFlow
# (this code runs once, ring model initialization)
# “words” is not a real list (it’s a placeholder variable) so
# I can’t use “len”
cond = lambda i, h: i < tf.shape(words)[0]
cell = lambda i, h: rnn_unit(words[i], h)
i = 0
_, h = tf.while_loop(cond, cell, (i, h0))

基于动态计算图（dynamic computation graph）的方法与之前的方法有根本性不同，它有几十年的学术研究历史，其中包括了哈佛的 Kayak、自动微分库（autograd）以及以研究为中心的框架 Chainer和 DyNet。在这样的框架（也称为运行时定义（define-by-run））中，计算图在运行时被建立和重建，使用相同的代码为前向通过（forward pass）执行计算，同时也为反向传播（backpropagation）建立所需的数据结构。这种方法能产生更直接的代码，因为控制流程的编写可以使用标准的 for 和 if。它还使调试更容易，因为运行时断点（run-time breakpoint）或堆栈跟踪（stack trace）将追踪到实际编写的代码，而不是执行引擎中的编译函数。可以在动态框架中使用简单的 Python 的 for 循环来实现有相同变量长度的循环神经网络。

# PyTorch (also works in Chainer)
# (this code runs on every forward pass of the model)
# “words” is a Python list with actual values in it
h = h0
for word in words:
h = rnn_unit(word, h)

PyTorch 是第一个 define-by-run 的深度学习框架，它与静态图框架（如 TensorFlow）的功能和性能相匹配，使其能很好地适合从标准卷积神经网络（convolutional network）到最疯狂的强化学习（reinforcement learning）等思想。所以让我们来看看 SPINN 的实现。

代码

在开始构建网络之前，我需要设置一个数据加载器（data loader）。通过深度学习，模型可以通过数据样本的批处理进行操作，通过并行化（parallelism）加快训练，并在每一步都有一个更平滑的梯度变化。我想在这里可以做到这一点（稍后我将解释上述堆栈操作过程如何进行批处理）。以下 Python 代码使用内置于 PyTorch 的文本库的系统来加载数据，它可以通过连接相似长度的数据样本自动生成批处理。运行此代码之后，train_iter、dev_iter 和 test_itercontain 循环遍历训练集、验证集和测试集分块 SNLI 的批处理。

from torchtext import data, datasets
TEXT = datasets.snli.ParsedTextField(lower=True)
TRANSITIONS = datasets.snli.ShiftReceField()
LABELS = data.Field(sequential=False)train, dev, test = datasets.SNLI.splits(
TEXT, TRANSITIONS, LABELS, wv_type='glove.42B')TEXT.build_vocab(train, dev, test)
train_iter, dev_iter, test_iter = data.BucketIterator.splits(
(train, dev, test), batch_size=64)

你可以在 train.py中找到设置训练循环和准确性（accuracy）测量的其余代码。让我们继续。如上所述，SPINN 编码器包含参数化的 Rece 层和可选的循环跟踪器来跟踪句子上下文，以便在每次网络读取单词或应用 Rece 时更新隐藏状态；以下代码代表的是，创建一个 SPINN 只是意味着创建这两个子模块（我们将很快看到它们的代码），并将它们放在一个容器中以供稍后使用。

import torchfrom torch import nn
# subclass the Mole class from PyTorch’s neural network package
class SPINN(nn.Mole):
def __init__(self, config):
super(SPINN, self).__init__()
self.config = config self.rece = Rece(config.d_hidden, config.d_tracker)
if config.d_tracker is not None:
self.tracker = Tracker(config.d_hidden, config.d_tracker)

当创建模型时，SPINN.__init__ 被调用了一次；它分配和初始化参数，但不执行任何神经网络操作或构建任何类型的计算图。在每个新的批处理数据上运行的代码由 SPINN.forward 方法定义，它是用户实现的方法中用于定义模型向前过程的标准 PyTorch 名称。上面描述的是堆栈操作算法的一个有效实现，即在一般 Python 中，在一批缓冲区和堆栈上运行，每一个例子都对应一个缓冲区和堆栈。我使用转移矩阵（transition）包含的“shift”和“rece”操作集合进行迭代，运行 Tracker（如果存在），并遍历批处理中的每个样本来应用“shift”操作（如果请求），或将其添加到需要“rece”操作的样本列表中。然后在该列表中的所有样本上运行 Rece 层，并将结果推送回到它们各自的堆栈。

def forward(self, buffers, transitions):
# The input comes in as a single tensor of word embeddings;
# I need it to be a list of stacks, one for each example in
# the batch, that we can pop from independently. The words in
# each example have already been reversed, so that they can
# be read from left to right by popping from the end of each
# list; they have also been prefixed with a null value.
buffers = [list(torch.split(b.squeeze(1), 1, 0))
for b in torch.split(buffers, 1, 1)]
# we also need two null values at the bottom of each stack,
# so we can from the nulls in the input; these nulls
# are all needed so that the tracker can run even if the
# buffer or stack is empty
stacks = [[buf[0], buf[0]] for buf in buffers]
if hasattr(self, 'tracker'):
self.tracker.reset_state()
for trans_batch in transitions:
if hasattr(self, 'tracker'):
# I described the Tracker earlier as taking 4
# arguments (context_t, b, s1, s2), but here I
# provide the stack contents as a single argument
# while storing the context inside the Tracker
# object itself.
tracker_states, _ = self.tracker(buffers, stacks)
else:
tracker_states = itertools.repeat(None)
lefts, rights, trackings = [], [], []
batch = zip(trans_batch, buffers, stacks, tracker_states)
for transition, buf, stack, tracking in batch:
if transition == SHIFT:
stack.append(buf.pop())
elif transition == REDUCE:
rights.append(stack.pop())
lefts.append(stack.pop())
trackings.append(tracking)
if rights:
reced = iter(self.rece(lefts, rights, trackings))
for transition, stack in zip(trans_batch, stacks):
if transition == REDUCE:
stack.append(next(reced))
return [stack.pop() for stack in stacks]

在调用 self.tracker 或 self.rece 时分别运行 Tracker 或 Rece 子模块的向前方法，该方法需要在样本列表上应用前向操作。在主函数的向前方法中，在不同的样本上进行独立的操作是有意义的，即为批处理中每个样本提供分离的缓冲区和堆栈，因为所有受益于批处理执行的重度使用数学和需要 GPU 加速的操作都在 Tracker 和 Rece 中进行。为了更干净地编写这些函数，我将使用一些 helper（稍后将定义）将这些样本列表转化成批处理张量（tensor），反之亦然。

我希望 Rece 模块自动批处理其参数以加速计算，然后解批处理（unbatch）它们，以便可以单独推送和弹出。用于将每对左、右子短语表达组合成父短语（parent phrase）的实际组合函数是 TreeLSTM，它是普通循环神经网络单元 LSTM 的变型。该组合函数要求每个子短语的状态实际上由两个张量组成，一个隐藏状态 h 和一个存储单元（memory cell）状态 c，而函数是使用在子短语的隐藏状态操作的两个线性层（nn.Linear）和将线性层的结果与子短语的存储单元状态相结合的非线性组合函数 tree_lstm。在 SPINN 中，这种方式通过添加在 Tracker 的隐藏状态下运行的第 3 个线性层进行扩展。

图 2：TreeLSTM 组合函数增加了第 3 个输入（x，在这种情况下为 Tracker 状态）。在下面所示的 PyTorch 实现中，5 组的三种线性变换（由蓝色、黑色和红色箭头的三元组表示）组合为三个 nn.Linear 模块，而 tree_lstm 函数执行位于框内的所有计算。图来自 Chen et al. (2016)。

7. 怎样用递归的方法遍历栈

如何用栈实现递归与非递归的转换
分类： C/C++2010-07-12 14:4012人阅读评论(0)收藏举报
如何用栈实现递归与非递归的转换一.为什么要学习递归与非递归的转换的实现方法? 1)并不是每一门语言都支持递归的. 2)有助于理解递归的本质. 3)有助于理解栈,树等数据结构.二.递归与非递归转换的原理. 递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的. 学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了. 1)前序遍历 a)递归方式:
void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */
{
if (T) {
visit(T); /* 访问当前结点 */
preorder_recursive(T->;lchild); /* 访问左子树 */
preorder_recursive(T->;rchild); /* 访问右子树 */
}
}
复制代码
b)非递归方式
void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法 */
{
initstack(S);
push(S,T); /* 根指针进栈 */
while(!stackempty(S)) {
while(gettop(S,p)&&p) { /* 向左走到尽头 */
visit(p); /* 每向前走一步都访问当前结点 */
push(S,p->;lchild);
}
pop(S,p);
if(!stackempty(S)) { /* 向右走一步 */
pop(S,p);
push(S,p->;rchild);
}
}
}
复制代码
2)中序遍历 a)递归方式
void inorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */
{
if (T) {
inorder_recursive(T->;lchild); /* 访问左子树 */
visit(T); /* 访问当前结点 */
inorder_recursive(T->;rchild); /* 访问右子树 */
}
}
复制代码
b)非递归方式
void inorder_nonrecursive(Bitree T)
{
initstack(S); /* 初始化栈 */
push(S, T); /* 根指针入栈 */
while (!stackempty(S)) {
while (gettop(S, p) && p) /* 向左走到尽头 */
push(S, p->;lchild);
pop(S, p); /* 空指针退栈 */
if (!stackempty(S)) {
pop(S, p);
visit(p); /* 访问当前结点 */
push(S, p->;rchild); /* 向右走一步 */
}
}
}
复制代码
3)后序遍历 a)递归方式
void postorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */
{
if (T) {
postorder_recursive(T->;lchild); /* 访问左子树 */
postorder_recursive(T->;rchild); /* 访问右子树 */
visit(T); /* 访问当前结点 */
}
}
复制代码
b)非递归方式
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有mark域的结点指针类型 */
void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法 */
{
PMType a;
initstack(S); /* S的元素为PMType类型 */
push (S,{T,0}); /* 根结点入栈 */
while(!stackempty(S)) {
pop(S,a);
switch(a.mark)
{
case 0:
push(S,{a.ptr,1}); /* 修改mark域 */
if(a.ptr->;lchild)
push(S,{a.ptr->;lchild,0}); /* 访问左子树 */
break;
case 1:
push(S,{a.ptr,2}); /* 修改mark域 */
if(a.ptr->;rchild)
push(S,{a.ptr->;rchild,0}); /* 访问右子树 */
break;
case 2:
visit(a.ptr); /* 访问结点 */
}
}
}
复制代码
4)如何实现递归与非递归的转换 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递 给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调 函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数. 所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存 就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现 同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上 面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三 种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以 得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次 处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明:
void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */
{
if (T) {
visit(T); /* 访问当前结点 */
preorder_recursive(T->;lchild); /* 访问左子树 */
preorder_recursive(T->;rchild); /* 访问右子树 */
}
}
复制代码
visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->;lchild)就是把当前 数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a) 确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结 构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用 树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的 "叶子结点". 三.三个例子 好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识 .即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明 白(事实上我也是花了两个星期的时间才弄得比较明白得). 1)例子一:
f(n) = n + 1; (n <2)
f[n/2] + f[n/4](n >;= 2);

这个例子相对简单一些,递归程序如下:
int f_recursive(int n)
{
int u1, u2, f;
if (n < 2)
f = n + 1;
else {
u1 = f_recursive((int)(n/2));
u2 = f_recursive((int)(n/4));
f = u1 * u2;
}
return f;
}
复制代码
下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点 ,我们看到当n < 2时f = n + 1,这就是返回的语句,有人问为什么不是f = u1 * u2,这也是一个 返回的语句呀?答案是:这条语句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之后 执行的,是这两条语句的父结点. 其次,什么是当前结点,由上面的分析,f = u1 * u2即是父结点 .然后,顺理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分别是左子树和右子 树了.最后,我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树.好了,树的情况分析 到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中,在上面给出的后序遍历的如果这个过程你没 非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域;另外,u1,u2和 每次调用递归函数时的n/2和n/4参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量 和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也 只有在向上返回时才用到,因此可以把这两个栈合为一个栈.如果对于上面的分析你没有明白,建 议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和 栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,最好把递归调用树和 栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里. ok,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来 的).
int f_nonrecursive(int n)
{
int stack[20], flag[20], cp;

/* 初始化栈和栈顶指针 */
cp = 0;
stack[0] = n;
flag[0] = 0;
while (cp >;= 0) {
switch(flag[cp]) {
case 0: /* 访问的是根结点 */
if (stack[cp] >;= 2) { /* 左子树入栈 */
flag[cp] = 1; /* 修改标志域 */
cp++;
stack[cp] = (int)(stack[cp - 1] / 2);
flag[cp] = 0;
} else { /* 否则为叶子结点 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 1: /* 访问的是左子树 */
if (stack[cp] >;= 2) { /* 右子树入栈 */
flag[cp] = 2; /* 修改标志域 */
cp += 2;
stack[cp] = (int)(stack[cp - 2] / 4);
flag[cp] = 1;
} else { /* 否则为叶子结点 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 2: /* */
if (flag[cp - 1] == 2) { /* 当前是右子树吗? */
/*
* 如果是右子树, 那么对某一棵子树的后序遍历已经
* 结束,接下来就是对这棵子树的根结点的访问
*/
stack[cp - 2] = stack[cp] * stack[cp - 1];
flag[cp - 2] = 2;
cp = cp - 2;
} else
/* 否则退回到后序遍历的上一个结点 */
cp--;
break;
}
}
return stack[0];
}
复制代码
算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示 已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.b)每 遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据 访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向. 2)例子二 快速排序算法 递归算法如下:
void swap(int array[], int low, int high)
{
int temp;
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
int partition(int array[], int low, int high)
{
int p;
p = array[low];
while (low < high) {
while (low < high && array[high] >;= p)
high--;
swap(array,low,high);
while (low < high && array[low] <= p)
low++;
swap(array,low,high);
}
return low;
}
void qsort_recursive(int array[], int low, int high)
{
int p;
if(low < high) {
p = partition(array, low, high);
qsort_recursive(array, low, p - 1);
qsort_recursive(array, p + 1, high);
}
}
复制代码
需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分, 左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分.这 里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实 partition函数就是对当前结点的访问). 再次进行递归调用树和栈的分析: 递归调用树:a)对当前结点的访问是调用partition函数;b)左子树: qsort_recursive(array, low, p - 1);c)右子树:qsort_recursive(array, p + 1, high); d)叶子结点:当low < high时;e)可以看出这是一个先序调用的二叉树 栈:要保存的数据是两个表示范围的坐标.
void qsort_nonrecursive(int array[], int low, int high)
{
int m[50], n[50], cp, p;
/* 初始化栈和栈顶指针 */
cp = 0;
m[0] = low;
n[0] = high;
while (m[cp] < n[cp]) {
while (m[cp] < n[cp]) { /* 向左走到尽头 */
p = partition(array, m[cp], n[cp]); /* 对当前结点的访问 */
cp++;
m[cp] = m[cp - 1];
n[cp] = p - 1;
}
/* 向右走一步 */
m[cp + 1] = n[cp] + 2;
n[cp + 1] = n[cp - 1];
cp++;
}
}
复制代码
3)例子三 阿克曼函数:
akm(m, n) = n + 1; (m = 0时)
akm(m - 1, 1); (n = 0时)
akm(m - 1, akm(m, n - 1)); (m != 0且n != 0时)
复制代码
递归算法如下:
int akm_recursive(int m, int n)
{
int temp;
if (m == 0)
return (n + 1);
else if (n == 0)
return akm_recursive(m - 1, 1);
else {
temp = akm_recursive(m, n - 1);
return akm_recursive(m - 1, temp);
}
}

8. 递归主方法

递归的主要方法是什么？

一、递归算法
递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
二、递归程序
在支持自调的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：

这一程序在Scheme语言中可以写作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不动点组合子
即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z 算子（英语：Z combinator）的不动点组合子，因此同样能达到递归的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
这一程序思路是，既然在这里函数不能调用其自身，我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。
尾部递归
尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能够解决的问题
数据的定义是按递归定义的。如Fibonacci函数。
问题解法按递归算法实现。如Hanoi问题。
数据的结构形式是按递归定义的。如二叉树、广义表等。
四、递归数据
数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
这一定义相当于宣告“一个链表或是空串行，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。