石家庄老站长

点击联系客服
客服QQ: 客服微信:
 找回密码
 立即注册
查看: 94|回复: 0

[C语言]学好递归3354递归 你要掌握的知识!

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-9-10 07:26:25 | 显示全部楼层 |阅读模式
文章目录

前言1,递归是什么?二、递归的两个必要条件3、递归如何运行4、递归与递归5、递归与递归的比较6、什么时候最后使用递归

前言

在一定的时间、空间限制下,人的体力有限,思考能力也有限,递归思维对实践最有用的指导方针是集中精力定义问题的关键。不用找解题的过程。正义(问题)解决(问题),正义解决!通过使大问题成为更小的问题并立即解决,可以很容易地解决函数本身定义的问题。因此,递归是编程中同样重要的知识点。

提示:本文内容如下

一、递归是什么?

让我们先看看定义。

程序调用自己的编程技术称为递归。

简单地说,就是从一个函数调用函数本身。

让我举个例子。

递归求第N个斐波那契数。

Int  Fib(int  n)

{

If  (n=2)

return  1;

Else

返回Fib(n-1) Fib
ken punctuation">(n - 2);
}
int main()
{
        //斐波那契数 1 1 2 3 5 8 13 21 34 51....,除前两位外,后一个数的值等于前两位相加
        int n = 0;
        printf("请输入你要查找的斐波那契数:");
        scanf("%d", &n);
        int ret=Fib(n);
        printf("你好,你要需要的值是:%d\n", ret);
        return 0;
}


所以,我们可以看到,所谓递归,其实就是一个函数里面调用函数自己本身。具体怎样调用的,我们下面再讲。

二、 递归的两个必要条件

1、存在限制条件,当满足这个限制条件的时候,递归便不再继续。
2、 每次递归调用之后越来越接近这个限制条件。


分析之后,我们可以得出两个点


1、结束条件
2、逼近条件


我们在使用递归的时候,需要满足这两个条件。

总结起来四个字——大事化小

继续举斐波那契数的例子:



三、递归是怎样运行的
我们通过一道题目来讲解。


题目: 递归实现n的k次方
内容: 编写一个函数实现n的k次方,使用递归实现。


【解决思路】
运用递归思路,我们只要找到递归结束条件和逼近条件。通过分析,我们可以画出下面这幅图。



【代码实现】

#include
double power(int n,int k)
{
        if (k 0)
        {
                k = -k;
                return 1 / (n*power(n, k - 1));
        }
        else if (k == 0)
                return 1;
        else if (k>0)
        {
                return n * power(n, k - 1);
        }
}
int main()
{
        int n = 0;
        int k = 0;
        printf("请输入一个整数:");
        scanf("%d", &n);
        printf("请输入要求的次方数:");
        scanf("%d", &k);
        double ret=power(n,k);
        printf("%1f\n", ret);
        return 0;
}

【画图详解递归思路】


通过图解,发现思路,我们** 存在限制条件k,当满足这个限制条件的时候,递归便不再继续。
每次递归调用之后越来越接近这个限制条件。**之后输出的时候就反过来回去。

这个就是递归的思路。

四、迭代与递归
不知大家有没有认真思考过上面的求斐波那契数的代码,它有什么问题?


如果我们这里求的是第50个斐波那契数呢?大家可以运行一下代码。可以发现,电脑运行了好久好久才算出结果,费时间。
如果求第10000个斐波那契数呢?程序就会崩溃。

为什么呢?
我们发现上面求斐波那契数的 Fib 函数 在调用的过程中很多计算其实在一直重复。
因为我们在调用这个函数的时候,除前两位外,后一个数的值等于前两位相加。这就导致了我们不断重复计算

如图:


我们可以看到,由于前两个数相加等于后一个数,前两个数相加等于后一个数,所以我们会不断产生重复的计算。就会造成计算量非常大,效率极低

那我们如何改进呢?
我们程序存东西的时候,存放在栈区。
如图:



在调试 例子中的Fib函数的时候,如果你的参数比较大,那就会报错: `stack overflow(栈溢出) 这样的信息。
系统分配给程序的栈空间是有限的,但是如果出现了死循环,或者(死递归),这样有可能导致一直开辟栈空间,最终产生栈空间耗尽的情况,这样的现象我们称为
栈溢出。

那如何解决上述的问题:


[ol]
  • 将递归改写成非递归。
  • 使用static对象替代non-static局部对象。在递归函数设计中,可以使用static对象替代nonstatic局 部对象(即栈对象),这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销,
    而且static对象还可以保存递归调用的中间状态,并且可为各个调用层所访问。[/ol]

    这里我们介绍迭代

    什么是迭代呢?
    【概念】


    迭代是重复反馈过程的活动,其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”,而每一次迭代得到的结果会作为下一次迭代的初始值。


    借用网上的图片来说明(侵删)


    目前对于c语言来说,迭代可以简单认为是循环结构。

    那么我们如何用迭代的方式求斐波那契数呢?
    【代码如下】

    int Fib(int n)
    {
            int a = 1;
            int b = 1;
            int c = 1;
            while (n>2)
            {
                    c = a + b;//求出c的值
                    a = b;//a赋值给b,也就是a作为b的值
                    b = c;//b赋值给c,也就是b作为c的值
                    n--;
            }
            return c;
    }
    int main()
    {
            // 1 1 2 3 5 8 13 21 34 55,除前两位外,后一个数的值等于前两位相加
            int n = 0;
            printf("请输入你要查找的斐波那契数:");
            scanf("%d", &n);
            int ret = Fib(n);
            printf("你好,你要需要的值是:%d\n", ret);
            return 0;
    }


    这样,我们算很大的数都能一下子算出来了,虽然不能保证正确,因为栈溢出了,但是效率很快。

    五、递归与迭代的比较
    我们用一个表格来分析:


    【注意】


    [ol]
  • 许多问题是以递归的形式进行解释的,这只是因为它比非递归的形式更为清晰。
  • 但是这些问题的迭代实现往往比递归实现效率更高,虽然代码的可读性稍微差些。
  • 当一个问题相当复杂,难以用迭代实现时,此时递归实现的简洁性便可以补偿它所带来的运行时开销。[/ol]

    六、 什么时候用递归
    什么时候用递归呢?


    (1)当解决一个问题时,递归和非递归都可以使用,且没有明显问题,那就可以使用递归
    (2)当解决一个问题时,递归写起来很简单,非递归比较复杂,且递归没有明显问题,那就用递归
    (3)如果说,用递归解决问题,写起来简单,但是有明显问题,那就不能使用递归



    最后
    以上内容是通过本人学习的理解和网上资料的整理梳理出来的递归与迭代的一些内容,有错漏之处,还请各位多多包涵与指出,共同进步,共同成长!
  • 回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|无图版|手机版|小黑屋|石家庄@IT精英团

    GMT+8, 2022-8-13 19:27 , Processed in 0.230605 second(s), 46 queries .

    Powered by Discuz! X3.4

    © 2001-2021 Comsenz Inc.

    快速回复 返回顶部 返回列表