C之递归函数（四十一）

我们今天来讲下递归，递归是一种数学上分而自治的思想。递归是需要边界条件的，当边界条件不满足时，递归将继续进行；当边界条件满足时，递归停止。递归是将大型复杂问题转化为与原问题相同但规模较小的问题进行处理。

创新互联专注于无极企业网站建设,响应式网站建设,购物商城网站建设。无极网站建设公司,为无极等地区提供建站服务。全流程定制开发，专业设计，全程项目跟踪，创新互联专业和态度为您提供的服务

函数体内部可以调用自己，它的函数体中存在自我调用的函数；递归函数是递归的数学思想在程序设计中的应用，递归函数必须有出口，函数的无限递归将导致程序栈溢出而崩溃。递归模型我们一般会表示成下面这样

C之递归函数（四十一）

我们下面用递归的方法编写函数求字符串长度，思想就是下面这样

C之递归函数（四十一）

具体代码如下

#include 

int strlen_r(const char* s)
{
    if( *s )
    {
        return 1 + strlen_r(s+1);
    }
    else
    {
        return 0;
    }
}

int main()
{
    printf("%d\n", strlen_r("abc"));
    printf("%d\n", strlen_r(""));
    
    return 0;
}

我们看看编译结果

C之递归函数（四十一）

结果如我们所想。下面我们来看看怎样用递归来实现斐波拉契数列：1，1，2，3，5，8，13，21，... 后面的每个数就是前面的两个数字和，用公式表示出来就是这样

C之递归函数（四十一）

我们来看看程序是怎样的

#include 

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

int main()
{
    printf("%d\n", fac(1));
    printf("%d\n", fac(2));
    printf("%d\n", fac(9));
    
    return 0;
}

前面两个肯定打印出来的都是1，第3个打印出来的是34,。我们来看看编译结果

C之递归函数（四十一）

我们下来再来看看递归在汉诺塔问题中的应用，如下所示，将木块借助 B 柱由 A 柱移动到 C 柱；每次只能移动一个木块；只能出现小木块在大木块之上；

C之递归函数（四十一）

我们来分解下这个问题，将 n - 1 个木块借助 C 柱由 A 柱移动到 B 柱；将最底层的唯一木块直接移动到 C 柱；将 n - 1 个木块借助 A 柱由 B 柱移动到 C 柱。我们来看看程序是怎么实现的

#include 

int han_move(int n, char a, char b, char c)
{
    if( n == 1 )
    {
        printf("%c ==> %c\n", a, c);
    }
    else
    {
        han_move(n-1, a, c, b);
        han_move(1, a, b, c);
        han_move(n-1, b, a, c);
    }
}

int main()
{
    han_move(3, 'A', 'B', 'C');
    
    return 0;
}

我们看看编译结果

C之递归函数（四十一）

我们看到已经正确实现了这个问题的解法。通过对递归的学习，总结如下：1、递归是一种将问题分而自治的思想；2、用递归解决问题首先要建立递归的模型；3、递归解法必须要有边界条件，否则无解！

欢迎大家一起来学习 C 语言，可以加我QQ：243343083。

标题名称：C之递归函数（四十一）
URL标题：http://cdiso.cn/article/pocsoi.html

C之递归函数（四十一）

其他资讯