1 min to read

椋鸟C语言笔记#13

递归、迭代及其弊端

Featured image

萌新的学习笔记,写错了恳请斧正。

递归

递归就是函数通过调用自己来达成 “大事化小小事化了” 的一种方式。

一般我们写递归需要添加限制条件,使函数在达到条件时能够终止递归,避免栈溢出。

递归时,内存的栈区不断开辟新的区域供函数使用。如果一个函数无限的或者大量的调用自己,整个可用的栈区空间都占满了,那么就会报错 Stackoverflow(栈溢出)。

举个例子,下面的 Fact 函数用来计算阶乘:

int Fact(int n)
{
    if (n <= 1)
        return 1;
    else
        return n * Fact(n-1);
}

我们可以发现,fact 函数不断的把阶乘函数拆分,把 Fact(n) 拆成 n*Fact(n-1)。直到某时 n 比 2 小了,才返回 1。具体的过程我们再拆分一下:

阶乘函数拆解示意图

我们发现,递归的过程,就是一步一步展开到不能再展开,随后再一步一步收拢的过程。

在计算 Fact(4) 时我们要先计算 Fact(3),而计算 Fact(3) 时要先计算 Fact(2),而在每一次展开时,上一级的展开式还在等待下一级的返回值,其所占的内存空间(函数栈帧)并不会被销毁。

阶乘用循环做更简单?那我们就再举一个例子:

斐波那契数列,其前两个元素均为 1,之后的元素等于其前两项的元素之和

int Feb(int n)
{
    if (1 == n || 2 == n)
        return 1;
    else
        return Feb(n-1) + Feb(n-2);
}

另外,没有返回值的函数也可以递归,只要在限制条件下调用自己即可:

void Print(int n)
{
    if(n>9)
        Print(n/10);
    printf("%d\n", n%10);
}

这就能按顺序打印数字的每一位了,其示意图如下:

打印函数拆解示意图

优缺点

优点:递归的逻辑过程相对简单容易理解与编写。

缺点:函数每次调用是都会向内存栈区申请一片空间,而递归时很容易因为一层一层的 “大事化小” 导致产生大量次级函数,当数字达到一定程度就容易造成栈溢出。也就是说,递归的层次越高,就越容易产生冗余计算。比如说上述的斐波那契数列,看着很简单不会占用多少内存,但我们令 n=40 时,Feb(2)就被调用了 63245986 次,而 feb(1)被调用了 39088169 次。这已经是一个庞大的数字了,但仅仅当 n=50 时,数字就进一步增长了很多个数量级(这时大多数计算机已经算不出来了因为光是 Feb(2)就被调用了 7778742049 次)。这就更不用说 n=100、200 甚至更高了。

迭代

迭代,通常以循环的方式呈现。

迭代一般有一个或多个不断的由旧值推出新值的变量,称为迭代变量。

而迭代时也需要设置限定条件,放置无限迭代陷入死循环(与栈溢出不同)。

一般我们会这样设计迭代程序:

比如说,上述斐波那契数列可以这么设计:

int Fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;
    while(n>2)
    {
        c = a+b;
        a = b;
        b = c;
        n--;
    }
    return c;
}

这样的运行效率要远远高于递归算法,也能够用来算更大的斐波那契数。

优缺点

很明显了,恰恰与递归相反。设计起来更复杂,但运行效率更高也更安全。