C语言函数递归
【摘要】 递归在书写的时候,有两个必要条件:1.递归存在限制条件,但凡满足这个限制条件时,递归便不再继续2.每次递归调用之后越来越接近这个限制条件递归的思想:把大事化小事递归其实就是函数自己调用自己//int main()//{// printf("hehe\n");// main();//再次调用main函数自己// return 0;//}////输出结果就是程序进入死循环,一直...
递归在书写的时候,有两个必要条件:
1.递归存在限制条件,但凡满足这个限制条件时,递归便不再继续
2.每次递归调用之后越来越接近这个限制条件
递归的思想:
把大事化小事
递归其实就是函数自己调用自己
//int main()
//{
// printf("hehe\n");
// main();//再次调用main函数自己
// return 0;
//}
////输出结果就是程序进入死循环,一直打印hehe
////总而言之,在函数中再次调用自己就是递归
////如果递归无限的递归下去,就会出现这样的错误,栈溢出
//
////每一次函数调用,都要为这次函数调用分配内存空间是内存的栈区上分配的,
//// 如果无限的递归调用函数,就会将栈区空间使用完,
//// 就会出现栈溢出的现象
//递归---求n的阶乘
//n的阶乘就是1~n的数字累计相乘
//n!=n*(n-1)!
//当n=0时,n的阶乘为1
//Fact(int n)//传参穿过来一个n
//{
// if (n == 0)
// return 1;
// else if (n > 0)
// return n * Fact(n - 1);//就是n*(n-1)!
//}
//
//
//
//int main()
//{
// int n = 0;
// scanf_s("%d", &n);
// int r = Fact(n);//n的阶乘
// printf("%d\n",r);
// return 0;
//}
//当输入数字是5的时候,n传上去的n是5,因为n>0,所以进行n * Fact(n - 1)、
//也就是n*(n-1)! 5*4!
//然后一次进行下去
//到最后,Fact(1)=1*Fact(0),因为Fact(0)=1,所以Fact(1)=1
//Fact(2)=2
//Fact(3)=6
//Fact(4)=24
//Fact(5)=120
//先递推再回归
//假设输入1234
// 1234%10=4
// 1234/10=123
// 123%10=3
// 123/10=12
// 12%10=2
// 12/10=1
// 1%10=1
// 1/10=0
//void print(int n)//接收n值
//{
// if (n > 9)
// print(n / 10);
// printf("%d ", n % 10);//打印余数
//}
//
//int main()
//{
// int n = 0;
// scanf_s("%d", &n);
// print(n);//传过去n值
//
// return 0;
//}
//假设n是123,大于9进去,先用print(123/10),把12的每一位打印出来
//上一步结束后,再打印123%10打印余数3
//原理:
//print(1234)
//print(123)+ 4
//print(12)+ 3 4
//print(1)+2 3 4 ***拆解到这一步然后返回依次打印
//代码的执行顺序是先print,再打印,
//你输入的数据进入print一直被拆分,知道拆分为1时就停止了,
// 然后再依次打印
//先是print(123)
//然后又进入print(123/10)也就是print(12)
//print(12)进去了print(12/10),也就是print(1),
//最后因为1<9,所以就先开始打印了1%10了,
//再返回打印12%10了,然后就是123%10
//最后的结果就是1 2 3
//只有print调用完才能轮到printf去打印
//print(1234)分成两部分-- - print(123)和printf("%d", 4)
//print(123)分成两部分---print(12)和printf("%d",3)
//print(12)分成两部分---print(1)和printf("%d",2)
如果函数不返回,函数所对应的栈帧空间就会一直被占用
不使用递归,使用迭代---循环的方式来解决问题
循环一定是迭代,但迭代不一定是循环
//求n的阶乘---循环迭代
int Fact(int n)
{
int i = 0;
int ret = 1;
for ( i = 1; i <= n; i++)
{
ret *= i;//就是ret = ret * i
}
return ret;
}
int main()
{
int n = 0;
scanf_s("%d", &n);
int r = Fact(n);
printf("%d", r);
return 0;
}
使用迭代的方式去求解,不仅可以解决问题,效率还更高
斐波那契数列
1 1 2 3 5 8 13 21 34 55
当n≤2时,第n个斐波那契数都是1,当n>2时,第n个斐波那契数就可以通过前两个数相加计算
若果求第n个斐波那契数列,用Fib(n)来表示,
当n>2的时候,Fib(n)=Fib(n-1)+Fib(n-2)
//求第n个斐波那契数
//若果求第n个斐波那契数列,用Fib(n)来表示,
//
//当n > 2的时候,Fib(n) = Fib(n - 1) + Fib(n - 2)
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int r=Fib(n);
printf("%d\n", r);
return 0;
}
当输入n为50,输出结果十分慢
//循环的方法求出第n个斐波那契数
//1 1 2 3 5 8 13 21 34 55
//求第3个数也就是求2,需要进行一次运算
//求第4个数的时候需要运算两次
//求第五个数的时候要运算3次。
//所以求第n个数的时候,要运算n-2次
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 0;
//n=1或者n=2的时候,可以不进入循环,n是3的时候大于2,就进去运算
while (n > 2)//仅仅只有当n>2的时候我们才进行计算
{
c = a + b;
a = b;
b = c;
n--;//当n是3的时候—1就是2,就不满足循环的条件
}//当n是4的=时候,c=1+1=2,然后b就变成下一个运算中的a了,
//第一个运算的c也变成第二个运算中的b了,然后第四个要求的数就是c了,
//第一次运算的时候运行了一次n--.所以变成了3,在第二次运行的时候再次
//运行就变成2了,就停止循环了
return c;
//当n=1时,不执行循环,直接返回c
//当n=2时,不执行循环,直接返回c
}
int main()
{
int n = 0;
scanf_s("%d", &n);
int r = Fib(n);
printf("%d", r);
return 0;
}
青蛙跳台阶
本质:斐波那契数列问题
当n>2时,有Fib(n-1) +Fib(n-2)中跳法
n=1时,有1中跳法
n=2时,有两种跳法
汉诺塔
游戏规则:大圆盘只能在下面,上面就放小圆盘
存在三个柱子 A B C
A上面有n个盘子,将最下面的盘子上面的n-1个盘子移动到B柱
然后把A仅剩的盘子挪到C柱
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)