LV020-递归函数

一个函数在它的函数体内调用它自身称为递归调用，这种函数称为递归函数。

执行递归函数的时候这个函数将反复调用其自身，每调用一次就进入新的一层，当最内层的函数执行完毕后，再一层一层地由里到外退出。

递归函数调用的执行过程分为两个阶段。

• 递推阶段：从原问题出发，按递归公式递推从未知到已知，最终达到递归终止条件。
• 回归阶段：按递归终止条件求出结果，逆向逐步代入递归公式，回归到原问题求解。

一、常见的两个问题

1. 阶乘问题

1.1 公式

在数学中，经常会看到阶乘：

$$n!=\{\begin{array}{ll}1& (n=0,1)\\ n\cdot (n-1)!& (n>1)\end{array}$$

1.2 c语言实现

那么我们用 C 语言怎么实现呢？

#include <stdio.h>

long factorial(int n);

int main(int argc, char *argv[])
{
    int a;

    printf("Input a number: ");
    scanf("%d", &a);

    printf("Factorial(%d) = %ld\n", a, factorial(a));
    return 0;
}

/* 求n的阶乘 */
long factorial(int n) 
{
    if (n == 0 || n == 1) 
	{
        return 1;
    }
    else 
	{
        return factorial(n - 1) * n;  /* 递归调用 */
    }
}

然后在终端运行以下命令：

gcc test.c -Wall # 编译程序
./a.out          # 执行可执行程序

接着我们会在终端中看到以下输出信息（根据提示，手动输入一个数字）：

Input a number: 5
Factorial(5) = 120

1.3 过程分析

接下来，我们可以分析一下， 5! 是怎么被求出来的。

• 递推阶段

层数	实参/形参	调用形式	需要计算的表达式	需要等待的结果
1	n=5	factorial(5)	factorial(4) * 5	factorial(4) 的结果
2	n=4	factorial(4)	factorial(3) * 4	factorial(3) 的结果
3	n=3	factorial(3)	factorial(2) * 3	factorial(2) 的结果
4	n=2	factorial(2)	factorial(1) * 2	factorial(1) 的结果
5	n=1	factorial(1)	1	无

• 回归阶段

层数	调用形式	需要计算的表达式	内层函数的返回值	表达式的值 （当次调用的结果）
5	factorial(1)	1	无	1
4	factorial(2)	factorial(1) * 2	factorial(1) 的返回值，也就是 1	2
3	factorial(3)	factorial(2) * 3	factorial(2) 的返回值，也就是 2	6
2	factorial(4)	factorial(3) * 4	factorial(3) 的返回值，也就是 6	24
1	factorial(5)	factorial(4) * 5	factorial(4) 的返回值，也就是 24	120

### 2. 斐波那契数列

2.1 数学公式

斐波那契数列是一个双层递归问题，它在一层中会调用自身两次。

$$F(n)=\{\begin{array}{ll}0& ,n=0\\ 1& ,n=1\\ F(n-1)+F(n-2)& ,n>1\end{array}$$

早研究这个数列的是斐波那契( Leonardo Fibonacci )，他当时是为了描述如下情况的兔子生长数目：

• 第一个月初有一对刚诞生的兔子
• 第二个月之后（第三个月初）它们可以生育
• 每月每对可生育的兔子会诞生下一对新兔子
• 兔子永不死去

第一个月小兔子没有繁殖能力，所以还是一对。两个月后，生下一对小兔对数共有两对。三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对。

于是按照这样的规律，得到一串的数字：斐波那契数列： 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , …… ，也就是说第一项和第二项是 1 ，之后的每一项为之前两项的和。

2.2 c语言实现

#include <stdio.h>
#include <time.h>

long fib(int n);

int main(int argc, char *argv[])
{
    int a;

    printf("Input a number: ");
    scanf("%d", &a);

    printf("fib(%d) = %ld\n", a, fib(a));

    return 0;
}

/* 求斐波那契数列 */
long fib(int n) 
{
    if (n < 1 )  return 0;
	else if(n == 1 || n == 2)  return 1;
    else return fib(n - 1) + fib(n - 2);
}

然后在终端运行以下命令：

gcc test.c -Wall # 编译程序
./a.out          # 执行可执行程序

按照提示输入一个数字， 接着我们会在终端中看到以下输出信息：

Input a number: 6
fib(6) = 8

二、编写思路

1. 递归条件

每一个递归函数都应该只进行有限次的递归调用，如果无限制递归，那么最终将会使栈空间溢出。

要想让递归函数逐层进入再逐层退出，需要解决两个方面的问题：

• 存在限制条件，当符合这个条件时递归便不再继续。例如，上边的 factorial() ，当形参 n 等于 0 或 1 时，递归就结束。
• 每次递归调用之后越来越接近这个限制条件。例如，上边的 factorial() ，每次递归调用的实参为 n - 1 ，这会使得形参 n 的值逐渐减小，越来越趋近于 1 或 0 。

2. 模板

• 第一步：找终止条件。最简单的情况是什么？直接返回什么？

// 阶乘：0! = 1
if (n == 0 || n == 1) return 1;

• 第二步：假设子问题已解决。相信递归能正确处理小一号的问题，直接调用：

// 阶乘：假设 (n-1)! 已经算出来了
factorial(n - 1)

• 第三步：组合结果。把子问题的结果和当前层组合：

// 阶乘
return n * factorial(n - 1);

• 最终实现

/* 求n的阶乘 */
long factorial(int n) 
{
    if (n == 0 || n == 1)  {
        return 1;
    }
    else {
        return n*factorial(n - 1);  /* 递归调用 */
    }
}

三、递归函数缺点

1. 内存占用

在程序占用的整个内存中，有一块内存区域叫做栈（ Stack ），它是专门用来给函数分配内存的，每次调用函数，都会将相关数据压入栈中，包括局部变量、局部数组、形参、寄存器、冗余数据等。

栈是针对线程来说的，每个线程都拥有一个栈。对每个线程来说，栈能使用的内存是有限的，一般是 1M~8M ，这在编译时就已经决定了，程序运行期间不能再改变。如果程序使用的栈内存超出最大值，就会发生栈溢出（ Stack Overflow ）错误。

Tips：常见编译器栈内存指定值

VC/VS 下，默认是 1M
C-Free 下，默认是 2M
Linux GCC 下，默认是 8M

【注意】这只是默认的栈内存大小，我们也可以通过参数来修改栈内存的大小。

发生函数调用时会将相关数据压入栈中，函数调用结束会释放这一部分内存。

对于递归函数，它的内部嵌套了对自身的调用，除非等到最内层的函数调用结束，否则外层的所有函数都不会调用结束。也就是说，外层函数暂停，一直处于等待状态，它要等待所有的内层函数调用完成后，它自己才能调用完成，完成后才能释放相应的内存。每一层的递归调用都会在栈上分配一块内存，有多少层递归调用就分配多少块相似的内存，所有内存加起来的总和是相当恐怖的，很容易超过栈内存的大小限制，这个时候就会导致程序崩溃。

2. 时间成本

每次调用函数都会在栈上分配内存，函数调用结束后再释放这一部分内存，内存的分配和释放都是需要时间的。每次调用函数还会多次修改寄存器的值，函数调用结束后还需要找到上层函数的位置再继续执行，这也是需要时间的。

斐波那契数列计算的时候递归 n 次，时间复杂度 O(2^n) ，可以很好的展示时间成本。

#include <stdio.h>
#include <time.h>

long fib(int n);

int main(int argc, char *argv[])
{
    int a;
	clock_t time_start, time_end;

    printf("Input a number: ");
    scanf("%d", &a);
	time_start = clock();
    printf("fib(%d) = %ld\n", a, fib(a));
	time_end = clock();
	printf("run time: %lfs\n", (double)(time_end - time_start)/ CLOCKS_PER_SEC );
    return 0;
}

/* 求斐波那契数列 */
long fib(int n) 
{
    if (n < 1 )  return 0;
	else if(n == 1 || n == 2)  return 1;
    else return fib(n - 1) + fib(n - 2);
}

然后在终端运行以下命令：

gcc test.c -Wall # 编译程序
./a.out          # 执行可执行程序

按照提示输入一个数字， 接着我们会在终端中看到以下输出信息：

Input a number: 50
fib(50) = 12586269025
run time: 42.039191s

42 秒的时间，这个时间成本有些过高了。

3. 用迭代代替？

递归函数的内存成本和时间成本是函数实现原理层面的缺陷，无法优化。但是呢，很多能用递归解决的问题也能用迭代来解决。迭代，其实就是就是循环。与递归函数相比，迭代不但没有额外的内存成本，也没有额外的时间成本。

#include <stdio.h>
#include <time.h>

long fib_recursion(int n);
long fib_iteration(int n);

int main(int argc, char *argv[])
{
    int a;
	clock_t time_start_recursion, time_end_recursion;
    clock_t time_start_iteration, time_end_iteration;

    printf("Please input a number: ");
    scanf("%d", &a);

    /* 递归的时间 */
    time_start_recursion = clock();
    printf("Fib_recursion(%d) = %ld\n", a, fib_recursion(a));
    time_end_recursion = clock();
    printf("run time with recursion: %lfs\n", (double)(time_end_recursion - time_start_recursion) / CLOCKS_PER_SEC );
    /* 迭代的时间 */
    time_start_iteration = clock();
    printf("Fib_iteration(%d) = %ld\n", a, fib_iteration(a));
    time_end_iteration = clock();
    printf("run time with iteration: %lfs\n", (double)(time_end_iteration - time_start_iteration) / CLOCKS_PER_SEC);

    return 0;
}

/* 求斐波那契数列 --- 递归 */
long fib_recursion(int n) 
{
    if (n < 1 )  return 0;
	else if(n == 1 || n == 2)  return 1;
    else return fib_recursion(n - 1) + fib_recursion(n - 2);
}

/* 求斐波那契数列 --- 迭代 */
long fib_iteration(int n)
{
    long result;
    long previous_result;
    long next_older_result;
    result = previous_result = 1;
    while (n > 2) 
	{
        n -= 1;
        next_older_result = previous_result;
        previous_result = result;
        result = previous_result + next_older_result;
    }
    return result;
}

然后在终端运行以下命令：

gcc test.c -Wall # 编译程序
./a.out          # 执行可执行程序

按照提示输入一个数字， 接着我们会在终端中看到以下输出信息：

Please input a number: 50
Fib_recursion(50) = 12586269025
run time with recursion: 45.457606s
Fib_iteration(50) = 12586269025
run time with iteration: 0.000005s

这个时间差距是显而易见的。