文章目录

前言

终于把函数这一章上完了，虽然因为我的摸鱼，两周都没有写完这个博客~这一期讲了递归、地址与数组初始化，关于指针的内容我想放在一个专题来讲，所以这节就简单介绍。

递归

递归（recursion）简单来说就是The function calls itself.即程序调用自身的编程技巧称为递归。

例如：

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？"从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？'从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？…

构成递归需具备的条件：
1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

一般来说可以使用循环的地方通常都可以使用递归。有时用循环解决问题比较好，但有时用递归更好。递归方案更简洁，但效率却没有循环高。

尾递归

最简单的递归形式是把递归调用置于函数的末尾，即正好在return语句之前。这种形式的递归被称为尾递归(tail recursion)，因为递归调用在函数的末尾。尾递归是最简单的递归形式，因为它相当于循环。

我们看一个关于计算阶乘的问题：有这么一个函数

double factorial(unsigned int i)
{
   if(i <= 1)
   {
      return 1;
   }
   return i * factorial(i - 1);
}

在每次递归后都以return结束当前次数的递归，可以减少对资源的消耗，提高效率。

递归与循环的选择

既然用递归和循环来计算都没问题，那么到底应该使用哪一个？

一般而言，选择循环比较好。

首先，每次递归都会创建一组变量，所以递归使用的内存更多，而且每次递归调用都会把创建的一组新变量放在栈中。递归调用的数量受限于内存空间。

其次，由于每次函数调用要花费一定的时间，所以递归的执行速度较慢。

但是在某些情况下，不能用简单的循环代替递归。

递归和倒序计算

递归在处理倒序时非常方便（在解决这类问题中，递归比循环简单）。

当你要倒序输出时，使用递归可以直接输出倒序。因为在递归判断结束时，会跳回上一次递归的下方语句，在这个地方添加输出就可以实现倒序输出了。

递归的缺点

前面也说了递归会耗费很多的内存，特别是双递归以上时，例如我们计算斐波那契数列。

int fibonaci(int i)
{
    if(i == 0)
       return 0;   
    if(i == 1)
       return 1;
    return fibonaci(i-1) + fibonaci(i-2);
}

由数学定义，斐波那契数列满足：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

假设调用Fibonacci(40)。第1级递归调用，将创建一个变量n。然后在该函数中要调用Fibonacci(）两次，在第2级递归中要分别创建两个变量n。这两次调用中的每次调用又会进行两次调用，因而在第3级递归中要创建4个名为n的变量。此时总共创建了7个变量。由于每级递归创建的变量都是上一级递归的两倍，所以变量的数量呈指数增长，这样内存会被大大消耗，很容易导致程序崩溃。

简单来说就是：递归是个好东西，就是效率不行