算法小专栏：递归与尾递归

AI科技园 10-24 79

前言：

现时我们对“java 尾递归”都比较注重，看官们都需要剖析一些“java 尾递归”的相关文章。那么小编在网摘上汇集了一些关于“java 尾递归””的相关内容，希望朋友们能喜欢，同学们快快来了解一下吧！

算法小专栏：递归与尾递归

级别： ★☆☆☆☆

标签：「算法」「递归」「recursion」

作者： MrLiuQ

审校： QiShare团队

本篇将介绍递归与尾递归的相关内容。

一、什么是“递归”？

递归是一种优雅的解决问题的方法。

看一段最简单的递归例子：

Fibonacci数（斐波那契数）：我们都知道Fibonacci数的递推公式为：

F(0)=F(1)=1，当n>=2时，F(n)=F(n-1)+F(n-2)

用Python写，就是这样：

def Fibonacci(n): if(n>=2): return Fibonacci(n - 1) + Fibonacci(n - 2) elif (n==0 or n==1): return 1 else: return -1print Fibonacci(20)复制代码

递归，简单来说，就是在运行的过程中调用自己。

递归能帮我们处理一些复杂的算法问题，但绝不能滥用递归。在程序设计角度，循环的性能要好于递归。从开发角度，使用递归，逻辑上更容易被理解。所以，要分场合使用递归，用好递归。

二、基线条件和递归条件

一个递归的实现一定少不了基线条件和递归条件。

那么，什么是“基线条件”？什么又是“递归条件”呢？

名称描述递归条件函数调用自己的条件。基线条件函数不再调用自己的条件，从而避免形成无限循环。

拿上面Fibonacci的例子来说，

def Fibonacci(n): if(n>=2): return Fibonacci(n - 1) + Fibonacci(n - 2) elif (n==0 or n==1): return 1 else: return -1复制代码

递归条件：就是 if(n>=2)。基线条件：就是 elif (n==0 or n==1)。

PS：在python中，else if的语法是elif。

三、栈

本节涉及到了内存方面的知识——调用栈（call stack）。

栈是一种简单的数据结构，当我们调用方法时，系统会执行“压栈”操作；当我们调用完方法时，系统会执行“出栈”操作。

简单来说，

函数调用就意味着 => 申请栈帧，函数入栈。函数返回就意味着 => 推出栈帧，函数出栈。

PS：不过还有一种特殊的情况：叫做尾调用优化（其本质是复用栈帧，即函数调用时，不再申请新栈帧，而是复用旧的栈帧。），在下文3.3节会重点讲解。

3.1 调用栈

我们来看这样一段代码：

def func1(param1): func2(param1) func3(param1)def func2(param2): print param2def func3(param3): print param3func1(647)复制代码

解析：定义了三个函数，分别是func1、func2、func3。其中传入的参数名为param1、param2、param3。

而在内存中，会做如下操作：

3.2 递归调用栈

递归函数也会使用调用栈，我们称之为“递归调用栈”。

下面，请看这个例子：

def factorial(x): if x == 1: return 1 else: return x * factorial(x-1)print factorial(3)复制代码

解析：这是一个求阶乘的递归函数。传入参数x，得出x*x-1...*1的值（x>=1）。而每一次递归，都会申请一个栈帧，这种栈帧就叫做递归调用栈。

图解如下：

3.3 尾递归

尾递归是一种高级递归方式，它可以不断的复用旧栈帧，已达到最大的内存优化。

注意：不是所有语言都支持尾递归优化（尾调用优化）。

JavaScript、Objective-C、Java、C++等支持尾递归优化，而Python本身是不支持尾递归优化的。

（关于iOS中OC的尾调用优化可以看这篇：iOS objc_msgSend尾调用优化机制详解）

Q1：什么是尾递归？什么又是尾调用？

尾递归：在函数最后一步，仅仅返回调用了自身。（注意仅仅两字）尾调用：在函数最后一步，仅仅返回了一个函数。（注意仅仅两字）所以，尾递归实际上是属于尾调用的一种特殊情形。

Q2：举个尾递归的例子？

int fun(int x) { if (x > 0) return fun(x-1); else return 1;}复制代码

在函数的最后一步，仅仅return了本身的函数。符合尾递归。

Q3：尾递归究竟做了什么优化？

两张对比图一目了然：

非尾调用：是尾调用：

Q4：尾递归的本质是什么？

答：栈帧的重复利用。

小编微信：可加并拉入《QiShare技术交流群》。

关注我们的途径有：

QiShare(简书)

QiShare()

QiShare(知乎)

QiShare(GitHub)

QiShare(CocoaChina)

QiShare(StackOverflow)

QiShare(微信公众号)