网站设计流程大致分为几个阶段,嘉兴网站开发公司电话,那个网站招丑的人做网红,域名解析 网站建设文章目录 一、递归举例二、递归举例2.1求n的阶乘2.2 顺序打印⼀个整数的每⼀位 三、递归与迭代3.1递归的思考3.2求第n个斐波那契数 总结 一、递归举例
.通过上回#xff08;【C语言】函数的系统化精讲#xff08;二#xff09;#xff09;我们了解到递归的限制条件#x… 文章目录 一、递归举例二、递归举例2.1求n的阶乘2.2 顺序打印⼀个整数的每⼀位 三、递归与迭代3.1递归的思考3.2求第n个斐波那契数 总结 一、递归举例
.通过上回【C语言】函数的系统化精讲二我们了解到递归的限制条件递归在书写的时候有2个必要条件 递归在书写时有两个必要条件 • 递归必须有一个限制条件当满足该条件时递归停止。 • 每次递归调用后逼近该限制条件。 下面我们来进行递归举例更加深刻了解一下吧
二、递归举例
2.1求n的阶乘
计算n的阶乘不考虑溢出n的阶乘就是1~n的数字累积相乘。 分析 我们知道n的阶乘的公式 n n ∗ (n − 1)! 比如 5 5 * 4 * 3 * 2 * 1 4! 4 * 3 * 2 * 1 所以我们可以直接55* 4 这样思考的话我们就可以把一个大的问题转换成一个规模较小又与原问题相似问题来进行求解 再稍微分析⼀下当 n0 的时候n的阶乘是1其余n的阶乘都是可以通过上述公式计算。 n的阶乘的递归公式如下
代码
int Fact(int n)
{if (n 0)return 1;elsereturn n * Fact(n - 1);
}
int main()
{int n 0;scanf(%d, n);int ret Fact(n);printf(%d\n, ret);return 0;
} 当然这里n的值不考虑太大的情况n太大会导致栈溢出
2.2 顺序打印⼀个整数的每⼀位
输⼊⼀个整数m打印这个按照顺序打印整数的每⼀位。 ⽐如 输⼊1024 输出1 0 2 4 输⼊520 输出5 2 0 分析 首先我们看1024怎么得到这个数的每⼀位呢 1024%10就能得到4然后1024/10得到102这就相当于去掉了4 然后继续对102%10就得到了2再除10去掉2以此类推 不断的 %10 和 \10 操作直到1234的每⼀位都得到 但是这⾥有个问题就是得到的数字顺序是倒着的 但是我们有了灵感我们发现其实⼀个数字的最低位是最容易得到的通过%10就能得到 那我们假设想写⼀个函数Print来打印n的每⼀位如下表⽰ Print(1024)|└── Print(102)|└── Print(10)|└── Print(1)|└── Print(0)在这个示意图中从最右边的数字开始递归调用Print函数每次都打印出当前数字的最后一位然后将问题规模减小直到数字变成0为止。具体的过程如下 调用Print(1024)。Print(1024)调用Print(102)。Print(102)调用Print(10)。Print(10)调用Print(1)。Print(1)调用Print(0)。Print(0)直接返回不做任何处理。Print(1)返回打印出1然后返回到调用它的函数。Print(10)返回打印出0然后返回到调用它的函数。Print(102)返回打印出2然后返回到调用它的函数。Print(1024)返回打印出1然后函数执行结束。 11代码
# define _CRT_SECURE_NO_WARNINGS 1
#include stdio.hvoid Print(int n)
{if (n 9){Print(n / 10);}printf(%d , n % 10);
}
int main()
{int m 0;scanf(%d, m);Print(m);return 0;
}三、递归与迭代
3.1递归的思考
递归是一种有用的编程技巧但像其他技巧一样也容易被误用。举例来说看到推导的公式很容易就被写成递归的形式犹如数学函数一样。
int Fact(int n)
{if(n0)return 1;elsereturn n*Fact(n-1);
}Fact函数是可以产⽣正确的结果但是在递归函数调⽤的过程中涉及⼀些运⾏时的开销。 什么是运行时的开销呢 在C语言中每次函数调用都需要在栈区为本次函数调用申请一块内存空间用来保存函数调用期间的各种局部变量的值。这块空间被称为运行时堆栈或者函数栈帧。如果函数没有返回对应的栈帧空间就会一直被占用。因此如果函数调用中存在递归调用每次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。因此如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stack overflow的问题。 所以如果不想使用递归就得想其他的办法通常就是迭代的方式通常就是循环的方式。 ⽐如计算n的阶乘也是可以产⽣1~n的数字累计乘在⼀起的。
int Fact(int n)
{int i 0;int ret 1;for (i 1; i n; i){ret * i;}return ret;
}
int main()
{int n 0;scanf(%d, n);int ret Fact(n);printf(%d\n, ret);return 0;
}上述代码是能够完成任务并且效率是⽐递归的⽅式更好的。 事实上我们看到的许多问题是以递归的形式进⾏解释的这只是因为它⽐⾮递归的形式更加清晰 但是这些问题的迭代实现往往⽐递归实现效率更⾼。 当⼀个问题⾮常复杂难以使⽤迭代的⽅式实现时此时递归实现的简洁性便可以补偿它所带来的运⾏时开销。 3.2求第n个斐波那契数
我们还可以举出更极端的例子比如计算第n个斐波那契数不适合使用递归求解但是斐波那契数的问题通常是用递归的形式描述的如下: 看到这公式很容易想到这还不简单啊将代码递归的形式走起如
int Fib(int n)
{if(n2)return 1;elsereturn Fib(n-1)Fib(n-2);
}当我们输入为50时光标还在闪烁需要很长时间才能算出结果这个计算所花费的时间是我们很难接受的这也说明递归的写法是非常低效的那是为什么呢 此时程序并没有停止而是不断的计算我们可以CtrlShiftEsc打开任务管理器我们可以看到我们的程序的CPU占比13.7%这个13.7%不是最高的由于代码运行起来后电脑便会风扇转起直接CPU干起来博主电脑无法立刻截不了图所以导致截图不到想要的高CPU运行百分比推荐你们也可以尝试一下 其实递归程序会不断的展开在展开的过程中我们很容易就能发现在递归的过程中会有重复计算⽽且递归层次越深冗余计算就会越多。 这里我们发现在计算第40个斐波那契数时使用递归方式会导致第3个斐波那契数被重复计算了39088169次这些计算是非常冗余的。因此斐波那契数的计算采用递归是非常不明智的我们应该考虑使用迭代的方式来解决。 我们知道斐波那契数的前2个数都是1然后前2个数相加就是第3个数那么我们从前往后从小到大计算就可以了。
这样就有下⾯的代码
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;
}总结
递归虽好但是也会引⼊⼀些问题所以我们⼀定不要迷恋递归适当就好。 递归和循环的选择 1如果使用递归写代码非常容易写出的代码没问题那就使用递归。 2如果递归写出的问题是存在明显的缺陷那就不能使用递归得用迭代的方式处理。
