赞
踩
函数递归是一种算法,递归是通过将问题分解为更小的子问题来解决问题的办法,递归的优点如下:
- 简洁性:递归可以用较少的代码实现复杂的功能
- 灵活性:递归可以应对未知深度的数据结构,因为它不需要提前知道要处理的嵌套层级
递归:程序调用自身的编程技巧称为递归;
- 从调用自身的层面:函数递归就是自己调用自己
- 从编程技巧层面:一种方法(它通常将一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解,简化程序的代码量),这种方法的主要思想为:将大事化小
- int main()
- {
- printf("hehe\n");
-
- main();
-
- return 0;
- }
main()函数内部调用了main()函数,产生的现象为程序死递归,导致栈溢出(stack overflow);
- 存在限制条件,当满足这个限制条件的时候,递归便不再继续;
- 每次递归调用之后越来越接近这个限制条件;
函数调用之前,操作系统会为其分配函数栈帧,从而保留函数调用时当前函数的参数;
当递归的最后一层执行结束,系统释放最后一次递归调用所开辟的空间,同时返回到上一级函数调用,接着向下执行程序,当上一级递归结束,系统继续释放该级调用的函数栈帧,按此循环,直至系统回收主函数所开辟的函数栈帧为止;
接受一个整型值(无符号),按照顺序打印它的每一位
输入:1234 输出:1 2 3 4
思路:
假设定义print()函数,其功能为按照顺序打印每一位
print(1234)即打印1 2 3 4
print(123) 4 按照顺序打印1 2 3,最后打印4;
print(12) 3 按照顺序打印1 2 ,最后打印3;
printf(1) 2 打印1,最后打印2;
当位数只有一位时,不需要进行拆分,直接打印;
- //只需要打印,不需要返回值
- void print(unsigned int x)
- {
- if (x > 9)
- {
- print(x / 10);//剥离n位数的前n-1位
- }
- printf("%d ", x % 10);//打印最后一位
- }
- int main()
- {
- unsigned int num = 0;
- scanf("%d", &num);
- print(num);
- return 0;
- }

运行结果:
画图分析:程序执行过程如箭头所示
- int my_strlen(char* s)
- {
- int count = 0;
- while (*s != '\0')
- {
- count++;
- s++;
- }
- return count;
- }
- int main()
- {
- char arr[] = "abc";
- int len = my_strlen(arr);
- printf("%d\n", len);
- return 0;
- }

思路:
假设my_strlen()函数可以求字符串长度,参数为字符指针
传参时需要传址,对字符地址进行解引用操作,如果第一个字符就是'\0',长度为0
如果第一个字符不是'\0',长度为1+my_strlen()函数;
例如:
my_strlen("abc")
1+my_strlen("bc")
1+1+my_strlen("c")
1+1+1+my_strlen("")
- int my_strlen(char* s)
- {
-
- if (*s == '\0')
- return 0;
- else
- return 1 + my_strlen(s + 1);
- }
- int main()
- {
- char arr[] = "abc";
- int len = my_strlen(arr);
- printf("%d\n", len);
- return 0;
- }
思路:
斐波那契数列:1 1 2 3 5 8 13 21 34 55 ......
斐波那契数的特点前两个数的和等于第三个数
公式:
当n<=2时, Fib(n)= 1
当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 ret = Fib(n);
- printf("%d\n", ret);
- return 0;
- }

递归的方式求解斐波那契数存在大量重复的计算,导致性能下降,效率低下,解决方案:
采用非递归方式求解
思路:
利用斐波那契数的特点,前两个斐波那契数不用计算
a=1 b=1 c=a+b=2
a=b=1 b=c=2 c=a+b=1+2=3
a=b=2 b=c=3 c=a+b=5
......
- //迭代解法
- //前两个斐波那契数不用计算,计算第n个斐波那契数即程序执行n-2次
- int Fib(int n)
- {
- int a = 1;
- int b = 1;
- int c = 1;
-
- while (n >= 3)
- {
- c = a + b;
- a = b;
- b = c;
-
- n--;
- }
- return c;
- }
- int main()
- {
- int n = 0;
- scanf("%d", &n);
- int ret = Fib(n);
- printf("%d\n", ret);
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。