赞
踩
递归是一种解决问题的方法,在C语言中,就是自己调用自己。
例如:
- #include<stdio.h>
- int main()
- {
- printf("hello\n");
- main();
- return 0;
- }
但是,如果递归无限地进行下去,就会出现栈溢出,上述就是一个典型例子。
并不是所有的递归都符合条件,上述的例子就不符合条件,递归有两个必要条件:
1.递归必须存在限制条件;
2.每次的递归结束之后,必须要越来越接近这个限制条件。
题目:计算n的阶乘
分析:要实现n的阶乘,还要运用递归的方法,我们可以把n!转化为n! = n * (n - 1 )!
代码实现如下:
- int Fact(int n)
- {
- if (n == 0)
- return 1;
- else
- return n * Fact(n - 1);
- }
-
- int main()
- {
- int n = 0;
- scanf("%d", &n);
- int r = Fact(n);
- printf("%d\n", r);
- return 0;
- }
从上述的代码中,我们可以看出,递归就是用少量的代码完成了大量的运算。
题目:输入一个数据,按照顺序打印整数的每一位
比如:输入:1234 输出: 1 2 3 4
代码实现如下:
- void Print(int n)
- {
- if (n > 9)
- Print(n / 10);
- printf("%d ", n % 10);
- }
-
- int main()
- {
- int n = 0;
- scanf("%d", &n);
- Print(n);
- return 0;
- }
递归的方法是一种很好的编程技巧,但是并不是在任何时候,递归的方法都适用,因此,在使用递归的方法之前还要慎重考虑!
C语言中每一次函数的调用,都需要为本次函数调用在内存中的栈区,申请一块内存空间来保存函数调用期间的各种局部变量的值,这块空间被称为运行时栈帧,或者函数栈帧。
如果再函数递归时,递归的层次太深,就会浪费太多的栈帧空间,也可能会出现栈溢出的现象。
如果不用递归的方式,通常我们会采用迭代的方式(循环的方式)。
例如上述求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 r = Fact(n);
- printf("%d\n", r);
- return 0;
- }
斐波那契数列:当n>=3时,在任意一个位置的数,等于前两个数的和,如:1 1 2 3 5...
如果我们考虑用递归的方法,则代码实现如下:
- 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的值比较小的时候,结果很快就可以得出来,但是,当n的值很大的时候,我们就会发现结果运行很慢。这就要考虑上述所说到的栈溢出的现象。
在这种情况下,就属于递归方法的错误使用,因此,我们要考虑使用迭代的方法进行解决,解决方法如下所示:
- int Fib(int n)
- {
- int a = 0;
- int b = 0;
- int c = 0;
- if (n <= 2)
- return 1;
- else
- {
- a = 1;
- b = 1;
- for (int i = 3; i <= n; i++)
- {
- c = a + b;
- a = b;
- b = c;
- }
- return c;
- }
- }
-
- int main()
- {
- int n = 0;
- scanf("%d", &n);
- int r = Fib(n);
- printf("%d\n", r);
- return 0;
- }
总结:递归可以简便运算的思路,但是,有些看似可以运用递归的问题,实际上是不可以的,因此,在运用递归的方法时,我们要慎重!
今天就到这里,我们下一个知识点再见~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。