深度剖析:递归

一,题记

最开始接触“递归”是在我学习 C 语言的时候,记得那时候和它“相识”感觉特别难理解。每当看书的时候就感觉书上讲的清晰明了、浅显易懂,但是当自己实践的时候,就感觉“困难重重”。

我相信每个人都知道:递归,就是一个函数调用自身。没错,递归的核心确实是这样。可是,为什么当我们自己实现的时候总是会遇到很多不清楚的地方呢?我想,大概是因为我们只是片面的理解了它的定义而已。

今天,就跟着小编一起深入“递归”的世界,希望通过这篇文章能够彻底的掌握“递归”。

二,递推

递归,包括:递推回归两部分。递推,是将原问题不断的分解成子问题,直到达到结束条件,返回最近子问题的解;

三,回归

回归,是在完成递推过程后逆向逐一回归,最终到达递推开始的原问题,返回原问题的解。以上这样的求解的过程就叫做“递归”。

四,递归原理

递归的基本原理如下:

1. 每一级的函数调用都有自己的变量;

2. 每一次函数调用都会有一次返回;

3. 递归函数中,位于递归调用前的语句和各级被调函数具有相同的执行顺序;

4. 递归函数中,位于递归调用后的语句和各级被调函数的顺序相反;

5. 虽然每一级都有自己的变量,但是函数代码并不会复制。函数代码是一系列的计算机指令,而函数调用就是从头执行这个指令集的一条命令。

6. 递归函数中必须包含可以终止递归的语句。

五,实战

下面通过学习递归最常见的例子——阶乘,来介绍一下递归的整体思路,开门见山的给出求 n 的阶乘的代码实现 (C++),如下:

Fac (int n){
   If (n<0) {
   Cout<<”n<0,
  data error!”<
   Return -1;
  }Else if (n == 0 || n == 1)
  {
   Return 1;
  }Else{
   Return n*Fac (n-1);
  }
}

根据上面的算法:试求5的阶乘

思路:5 的阶乘递归过程分为:递推和回归两步来分析。

第 1 步:递推

f29c3eb39e6e4dd9bec254397d5fbdd6-Snip2018032216.png

第 2 步:回归

0087ddf039ef49a08398110507d7e474-Snip2018032217.png

 

如果还感觉上面的步骤不清晰,下一次我们再通过“栈”的方式来详细的讲解一下。

【下节概要】:

“栈”的特性是:后进先出(last in first out);

[递归]:进栈——> 递推,出栈——> 回归;

作者:tom
原创链接: 深度剖析:递归
来源:本文首发架构中国
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。