Skip to content

递归

栈有一个很重要的应用:在程序设计语言中实现了递归。我们先来看一个经典的递归例子:斐波那契数列。

斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 特点:前面相邻两项之和,构成了后一项

斐波那契数列的实现

  1. 一对兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。假设所有的兔子都不死亡,那么一年以后可以繁殖多少对兔子呢?

    #include <stdio.h>
    
    // 斐波那契的递归函数 
    int Fbi(int i)
    {
        if (i < 2)
            return i == 0 ? 0 : 1;
        return Fbi(i-1) + Fbi(i-2);     
    }
    
    int main()
    {
        int i;
        for (i=1; i<=12; i++)
            printf("%d\n", Fbi(i));
        return 0;
    }
    
  2. 假设有 n 个台阶,每次你可以跨 1 个台阶或者 2 个台阶,请问走这 n 个台阶总共有多少种走法?

    #include <stdio.h>
    
    // 递归实现方式
    int f(int n)
    {
        if (n == 1) 
            return 1;
        if (n == 2)
            return 2;
        return f(n-1) + f(n-2);
    }
    
    // 迭代循环的非递归实现方式
    int f(int n)
    {   
        if (n == 1)
            return 1;
        if (n == 2) 
            return 2;
    
        int ret = 0;
        int pre = 2;
        int prepre = 1;
        int i;      
        for (i=3; i<=n; ++i) {
            ret = pre + prepre;
            prepre = pre;
            pre = ret;
        }
        return ret;
    }
    
    int main()
    {
        printf("%d\n", f(6)); // 6 个台阶总共有 13 种走法
        return 0;
    }
    

    下面分别为问题 1 和 2 的数学函数定义:

斐波那契数列

递归是一种应用非常广泛的算法(或者编程技巧),很多数据结构和算法的编码实现都要用到递归,比如图的深度优先搜索(DFS),二叉树的前中后序遍历递归实现。

递归代码简洁高效,但是也有很多弊端。比如堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等。

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*