-
2021-05-24 08:46:19
c语言递归算法如何实现
发布时间:2020-09-22 14:22:05
来源:亿速云
阅读:186
作者:小新
这篇文章将为大家详细讲解有关c语言递归算法如何实现,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
递归就是一个方法自己调用自己。在编程语言中,如果一个程序允许您在同一个函数中调用一个函数,那么它就被称为函数的递归调用。void recursion() {
recursion(); /* 函数调用本身 */
}
int main() {
recursion();
}
C语言支持递归,即一个调用自身的函数。但是在使用递归时,程序员需要小心定义函数的退出条件,否则它将进入无限循环。
递归函数对于解决许多数学问题非常有用,例如计算一个数的阶乘、生成斐波那契级数等。
数的阶乘
下面的例子使用递归计算一个给定的数的阶乘函数#include
unsigned long long int factorial(unsigned int i) {
if(i <= 1) {
return 1;
}
return i * factorial(i - 1);
}
int main() {
int i = 12;
printf("Factorial of %d is %d\n", i, factorial(i));
return 0;
}
输出:Factorial of 12 is 479001600
斐波那契系列
以下示例使用递归函数为给定数字生成斐波那契(Fibonacci)系列#include int fibonacci(int i) {
if(i == 0) {
return 0;
}
if(i == 1) {
return 1;
}
return fibonacci(i-1) + fibonacci(i-2);}int main() {
int i;
for (i = 0; i < 10; i++) {
printf("%d\t\n", fibonacci(i));
}
return 0;}
输出:0
1
1
2
3
5
8
13
21
34
关于c语言递归算法如何实现就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
更多相关内容 -
使用c语言递归删除指定文件夹下所有的文件(包含文件以及文件夹)
2018-12-20 09:50:16本代码使用c语言,可执行递归删除指定文件夹下所有的文件(包含文件以及文件夹)的操作,注释详细,易于使用或修改 -
C语言递归调用举例
2018-04-22 14:23:36C语言递归调用举例,可直接复制粘贴。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。... -
C语言递归算法
2018-12-03 17:35:07这是培训老师交的递归算法,还是挺可以的,感兴趣的伙计们可以看看 -
C语言递归实现线索二叉树
2020-12-31 11:59:51本文实例为大家分享了C语言递归实现线索二叉树的具体代码,供大家参考,具体内容如下 描述:将二叉树中结点的空左孩子指针域指向前驱结点,将空的右孩子指针域指向后继结点。 code: #pragma warning(disable:... -
C语言递归操作用法总结
2021-05-24 07:24:45本文实例总结了C语言递归操作用法。分享给大家供大家参考,具体如下:用归纳法来理解递归步进表达式:问题蜕变成子问题的表达式结束条件:什么时候可以不再是用步进表达式直接求解表达式:在结束条件下能够直接计算...本文实例总结了C语言递归操作用法。分享给大家供大家参考,具体如下:
用归纳法来理解递归
步进表达式:问题蜕变成子问题的表达式
结束条件:什么时候可以不再是用步进表达式
直接求解表达式:在结束条件下能够直接计算返回值的表达式
逻辑归纳项:适用于一切非适用于结束条件的子问题的处理,当然上面的步进表达式其实就是包含在这里面了。
递归算法的一般形式:
void func( mode)
{
if(endCondition)
{
constExpression //基本项
}
else
{
accumrateExpreesion //归纳项
mode=expression //步进表达式
func(mode) //调用本身,递归
}
}
最典型的就是N!算法,这个最具有说服力。理解了递归的思想以及使用场景,基本就能自己设计了,当然要想和其他算法结合起来使用,还需要不断实践与总结了。
#include "stdio.h"
#include "math.h"
int main(void)
{
int n, rs;
printf("请输入需要计算阶乘的数n:");
scanf("%d",&n);
rs = factorial(n);
printf("%d ", rs);
}
// 递归计算过程
int factorial(n){
if(n == 1) {
return 1;
}
return n * factorial(n-1);
}
递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件,这样就不会产生无限递归的情况了。
能用递归来解决的问题必须满足两个条件:
① 可以通过递归调用来缩小问题规模,且新问题与原问题有着相同的形式。
② 存在一种简单情境,可以使递归在简单情境下退出。
如果一个问题不满足以上两个条件,那么它就不能用递归来解决。
为了方便理解,还是拿斐波那契数列来说下:求斐波那契数列的第N项的值。
这是一个经典的问题,说到递归一定要提到这个问题。斐波那契数列这样定义:f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2)
这是一个明显的可以用递归解决的问题。让我们来看看它是如何满足递归的两个条件的:
1.对于一个n>2, 求f(n)只需求出f(n-1)和f(n-2),也就是说规模为n的问题,转化成了规模更小的问题;
2. 对于n=0和n=1,存在着简单情境:f(0) = 0, f(1) = 1。
因此,我们可以很容易的写出计算费波纳契数列的第n项的递归程序:
int fib(n){
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return f(n-1) + f(n-2);
}
在编写递归调用的函数的时候,一定要把对简单情境的判断写在最前面,以保证函数调用在检查到简单情境的时候能够及时地中止递归,否则,你的函数可能会永不停息的在那里递归调用了。
判断一个字符串是否是回文:
function huiwen($str)
{
if(strlen($str)==1 || strlen($str)==0){
return 1;
}else{
if($str[0]==$str[strlen($str)-1]){
$str = substr($str,1,-1);;
echo $str."
";return huiwen($str);
}else{
return 0;
}
}
}
希望本文所述对大家C语言程序设计有所帮助。
-
汉诺塔问题的c语言递归
2021-10-21 00:40:10关于汉诺塔问题的c语言递归 C语言递归程序代码如下: #include<stdio.h> int c=0; void move(char x,int n,char z) { printf("第%i步:将%i号盘从%c->%c\n",++c,n,x,z); } void hanoi(int n,char x,char y...汉诺塔问题的c语言递归
C语言递归程序代码如下:
#include<stdio.h> int c=0; void move(char x,int n,char z) { printf("第%i步:将%i号盘从%c->%c\n",++c,n,x,z); } void hanoi(int n,char x,char y,char z) { if(n==1) move(x,1,z); else { hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } } void main() { int n; while(printf("3个塔座为a、b、c,圆盘最初在a座,借助b座移到c座。请输入圆盘数:")!=EOF){ scanf("%d",&n); hanoi(n,'a','b','c'); } }
n层汉诺塔的移动步骤可以看成以下三步(汉诺塔从n到1逐渐减小):
1.n上面的n-1个汉诺塔移动到第三个柱子
2.n号汉诺塔移动到第二个柱子
3.将第二个柱子上的n-1个汉诺塔移动到第三个柱子
这样第1和第3所用的时间是相同的
四层汉诺塔的移动步骤如下图所示
仔细观察会发现第7步和第8步第四层汉诺塔的位置是相反的。
同样的在第6步和第9步中第一、四层的位置也是相反的。
那不难理解,在n层汉诺塔中,当第n层汉诺塔到达第三个柱子时,之后经历的步骤和将第n层汉诺塔从第一个柱子移动到第三个柱子的步骤是相对的(相对不是相反,相反只是指位置)
所以对于程序的实现,来读一读源代码。举例:n=1和n=2时程序的步骤
第一步
从main函数开始输入n(即代表n层汉诺塔),然后调用void hanoi(int n,char x,char y,char z)函数,输入n和a、b、c三个柱子。
跳转到hanoi函数进行判断
如果n=1,则直接调用move函数将第一层汉诺塔移动到c柱即可。
但当n>1时,则进入递归。
当n=2时,hanoi函数输入的参数如下hanoi(2-1,a,c,b);
第二步
再次进入hanoi,这时n=1,则将进行第一步,跳转进move函数,将第一层汉诺塔直接送到第三个柱子,即b柱。
程序跳回n=2时hanoi程序,这时执行move(a,2,c),即将第二层汉诺塔移动到c柱。
第三步
再次跳回到n=2时的hanoi程序,这次执行到了第二个hanoi函数,这时变成了hanoi(2-1,b,a,c),即第二层汉诺塔从b柱移动到了c柱。
将问题化为整体来看,当有n层汉诺塔时,程序运行步骤如下:
第一步:
将n-1层汉诺塔从a柱移动到b柱
第二步:
将第n层汉诺塔移动到c柱
第三步:
将n-1层汉诺塔从b柱移动到c柱
-
C语言递归算法(斐波那契数列)
2022-04-15 10:15:01一、什么是递归? 递归,就是在运行的过程中调用自己(套娃) 下面给出一个最简单的递归 #include<stdio.h> int main() { printf("%d", 1); main(); return 0; } 这段代码是main函数被递归调用,...一、什么是递归?
递归,就是在运行的过程中调用自己(套娃)
下面给出一个最简单的递归
#include<stdio.h> int main() { printf("%d", 1); main(); return 0; }
这段代码是main函数被递归调用,运行后结果框就会一直不停的打印“1”,最后导致栈溢出。
二、构成递归需具备的条件
1. 子问题须与原始问题为同样的事,且更为简单;
2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。
三、递归的应用(斐波那契数列)
#define _CRT_SECURE_NO_WARNINGS //忽略安全检测,不然使用scanf会报错 #include<stdio.h> int Fib(int n) { if (n<=2) { return 1; } else { return (Fib(n - 1) + Fib(n - 2)); } } int main() { int n ; scanf("%d", &n); printf("%d\n", Fib(n)); return 0; }
当输入n较小时,程序运行很快,但是当n值过大时,程序运行就会慢很多,执行起来效率很低
四、递归的缺点
递归算法解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
我们把代码加以修改,测试第三个斐波那契数的运算次数
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int count = 0; int Fib(int n) { if (n==3)//测试第三个斐波那契数的运算次数 { count++; } if (n<=2) { return 1; } else { return (Fib(n - 1) + Fib(n - 2)); } } int main() { int n ; int ret = 0; scanf("%d", &n); printf("%d\n", Fib(n)); printf("%d\n", count); return 0; }
当输入n为50时,第三个斐波那契数的运算次数就有512559680次
我们尝试不用递归算法,从而优化代码
#include<stdio.h> int Fib(int n) { int a=1; int b=1; int ret=1; { while (n>2) { ret = a + b; a = b; b = ret; n--; } return ret; } } int main() { int n ; int ret = 0; scanf("%d", &n); printf("%d\n", Fib(n)); return 0; }
五、递归算法一般用于解决三类问题:
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构,但用递归求解比迭代求解更简单,如Hanoi问题。
(3)数据的结构形式是按递归定义的。
如二叉树、广义表等,由于结构本身固有的递归特性,则它们的操作可递归地描述。
-
浅谈C语言递归算法.docx
2021-05-25 08:59:11浅谈C语言递归算法浅析C语言递归算法王浏江盐城师范学院 信息工程学院 计算机161班 摘要:递归算法,结构清晰,代码简练,函数调用灵活方便,比较容易理解和阅读。因此,递归算法一般用于多个相似小问题组成的一个... -
c语言递归算法怎么实现
2021-05-22 04:53:06递归就是一个方法自己调用自己。在编程语言中,如果一个...}C语言支持递归,即一个调用自身的函数。但是在使用递归时,程序员需要小心定义函数的退出条件,否则它将进入无限循环。递归函数对于解决许多数学问题非... -
c语言递归函数的使用方法
2021-05-20 10:34:09c语言递归函数的使用方法发布时间:2020-06-11 09:39:53来源:亿速云阅读:157作者:Leah这篇文章给大家分享的是c语言递归函数的使用方法。小编觉得挺实用的,因此分享给大家做个参考。一起跟随小编过来看看吧。递归... -
c语言递归系列总结
2021-01-24 18:00:36递归总结递归什么是递归递归的特点 结构 缺点递归的本质递归的应用递归实战阶乘阶乘递归解法阶乘普通解法斐波拉契数列斐波拉契数列递归解法 递归 什么是递归 递归简而言之就是函数自己调用自己 如图所示 但是递归并... -
C语言递归思想实现汉诺塔
2022-01-20 20:17:063.汉诺塔递归的c语言实现 1.递归思想简介 在c语言中,程序调用自身的编程技巧称为递归( recursion)。 递归的定义看上去似乎很抽象,使用代码描述能够让人容易理解,下面是一个函数递归的例子。 /* 递归求n... -
C语言 递归函数实现二分查找
2021-08-19 10:46:27C语言 递归函数实现二分查找 欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。 新的... -
C语言 递归法求阶乘
2020-08-30 18:18:05C语言 递归法求阶乘 利用一个函数进行递归求阶乘,但该数不能小于0,且若为0或1,得到的结果都为1,其他情况,对该数不断递归 #include <stdio.h> #include <stdlib.h> int main() { int fac(int n); /... -
c语言递归求阶乘
2020-04-10 20:46:08递归函数的定义: 先引入一个例子:输入n,求n!。 分析: n!= 1 * 2 * 3 * … * n 1)一般解法: #include"stdio.h" int main() { int n, i; double s = 0; scanf("%d", &n); for(i = 1;i <= n;i++) { ... -
C语言递归解决水洼问题
2022-04-03 21:28:55 -
C语言递归实现字符串反转(详解)
2022-05-07 20:14:43c语言递归实现字符数组反转,详细解析,代码一条一条运行搞懂 -
递归法_C语言递归法_递归算法经典实例
2021-05-25 07:27:02学知识,解决实际问题。(3)从简单问题出发,逐步增加难度,增强解决问题的能力。...四、教学重点与难点学习重点:掌握能针对具体问题找到递归出口、总结归纳出递归函数关系式。学习难点:正确高效的应用递归法分析、... -
C语言递归求阶乘
2020-03-26 19:47:47C语言递归求阶乘 #include <stdio.h> #include <stdlib.h> int fac(int n) { if (n <= 1) { return 1; } else { return n*fac(n - 1); } } int main() { ... -
C语言递归次数上限
2022-02-09 20:05:16C语言递归次数上限 ** 最近开始准备考研专业课,学习数据结构。根据例题实现代码的时候发现了如下问题 //printN递归实现 #include <stdio.h> void printN(int N) { if(N){ printN(N-1); printf("%d\n", N);... -
C语言递归函数(递归调用)详解[带实例演示]
2021-12-23 22:04:26递归函数不是C语言的专利,Java、C#、JavaScript、PHP等其他编程语言也都支持递归函数。 下面我们通过一个求阶乘的例子,看看递归函数到底是如何运作的。阶乘 n! 的计算公式如下: 根据公式编写如下的代码: ... -
C语言 递归
2021-12-12 19:10:23C语言,递归,函数 -
c语言递归实现十进制转换
2022-03-05 15:24:02#include<stdio.h> void func(int x) { if(x==1) printf("%d",x%2); else { func(x/2); printf("%d",x%2); } x%2 } int main() { int n=0; scanf("%d",&n); func(n); } -
C语言递归实现素数分解
2011-10-16 14:50:42C语言递归实现素数分解 C语言初学者必会 -
c语言递归实现圆周率PI的计算(精确到小数点后7位)
2021-08-07 17:30:521.算法来自李永乐老师的课程: ... 2.运行环境为linux64位服务器 3.编译命令:gcc main.c -lm -g 4.运行结果(入参为大于等于2的正整数,在17开始就不精确了) [root@localhost cacu_π]# ./a.out 16 ... -
C语言 递归算法及简单递归练习总结
2018-12-14 22:56:48递归 :大师 L. Peter Deutsch 说过:To Iterate is Human, to Recurse, Divine.中文译为:人理解迭代,神理解递归。 简单理解: 递归:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以... -
C语言递归/非递归方法实现斐波那契数列
2022-03-27 21:32:03众所周知,斐波那契数列就是后一项为前两项...用C语言实现斐波那契数列有三种方式 递归调用实现斐波那契数列 //斐波那契数列的递归实现 int Fun(int a)//时间复杂度O(2^n),空间复杂度O(n) { if (a <= 0) { r