递归(已解决)

august

C语言怎么实现用递归方法把  0,1,1,2,3,5,8,13,21,34,55...
给输出来呢?

secondsen

这个东西。。。

    for+数组
   
    输入x
    a[0] = 0
        a[1] = 1
    for i in 0..X
           a[x] = a[x-1] + a[x-2]
           print
        end
由于n年没有碰了。。所以写法文完全不记得了。。。。
不知道LZ要的是不是这个？

什么也不懂的我飘走。。。

突然下定决心要学C++

august

[s:5] 这样的话就不叫递归吧.......

shawind

这其实是数学问题吧，找出这些数字的规律，下面就好办了。

ps. 数学从来没有及格过的人路过.......

august

规律一看就出来了,问题是现在要用递归方法做出来 [s:6]

august

#include<stdio.h>

int array[10]={0,1};
void arr(int x)
{
     static int a=0;
     if(x>=2)
     {
         array[a+2]=array[a+2-1]+array[a+2-2];
         a++;
         arr(x-1);
     }
   
}
void main()
{
    int i;
    arr(5);
    for(i=0;i<5;i++)
        printf("%d ",array);
}
这样可以了,原来一直没把静态变量的问题处理好,所以搞不出来,现在可以了,谢谢 [s:1]

secondsen

难道我给思路的不对。。。。。。

不懂的我不再这丢人了。。。。 [s:5]

rednaxela

fib数列要递归做也没有必要用静态变量,除了那个数组外.如果只是为了输出而没有其它需求的话,那不用数组更好.说到底如果只要求一次fib数列的话最好不要递归,如果要多次求值且范围预先能估计到,那么最有效的方法是程序一开始就算一张表出来,后面运行时查表.

对应LZ的递归算法,应该这样才对:

1. /*
2. * fib.c
3. * 简单递归fibonacci数列算法演示
4. */
5. #include <stdio.h>
7. int array[10] = { 0, 1 };
9. int fib(int x) {
10.     switch (x) {
11.     case 0:
12.         return 0;
13.     case 1:
14.         return 1;
15.     default:
16.         array[x] = fib( x - 1 ) + fib( x - 2 );
17.         return array[x];
18.         /* basically you should just return the result
19.           instead of assigning the value into the array
20.           return fib( x - 1 ) + fib( x - 2 ); */
21.     }
22. }
24. void main() {
25.     int i;
27.     fib( 5 );
28.     for ( i = 0; i < 5; ++i ) {
29.         printf("%d ", array[i]);
30.     }
31. }

复制代码

但实际上这么做效率很低,估计LZ只需要这样就行了:

1. /*
2. * fib.c
3. * 简单循环fibonacci数列算法演示
4. */
5. #include <stdio.h>
7. int array[10] = { 0, 1 };
9. void fib(int x) {
10.     int i;
12.     for ( i = 2; i < x; ++i ) {
13.         array[ i ] = array[ i - 1] + array[ i - 2];
14.     }
15. }
17. void main() {
18.     int i;
20.     fib( 5 );
21.     for ( i = 0; i < 5; ++i ) {
22.         printf("%d ", array[i]);
23.     }
24. }

复制代码

尾递归是低效的,除非在特定的场景使用递归使语义特别清晰,否则还是避免使用尾递归的好.现代高级语言编译器一般会做尾递归消除的优化,但是不要太依赖这样的优化.

rednaxela

结果今天上午.NET期末考试的时候考了这数列...真神奇,从大二到大四年年都有它.写了个实现,发在了这里:
http://rednaxelafx.javaeye.com/blog/133377

lw

这个也是C++众值得骄傲的一个东西偶TOT也给个实现好了：

3. template<int f>
4. class FibCalc {
5. public:
6.     enum {
7.         n = FibCalc<f-2>::n + FibCalc<f-1>::n,
8.     };
9. };
11. template<>
12. class FibCalc<0> {
13. public:
14.     enum {
15.         n = 0,
16.     };
17. };
19. template<>
20. class FibCalc<1> {
21. public:
22.     enum {
23.         n = 1,
24.     };
25. };
27. // ---------------
29. #include <stdio.h>
30. template<int count>
31. class Printer : private FibCalc<count> {
32. public:
33.     Printer(void) { Printer<count-1>(); printf("%d ", n); }
34. };
36. template<>
37. class Printer<0> : private FibCalc<0> {
38. public:
39.     Printer(void) { printf("%d ", n); }
40. };
42. // ---------------
44. int main( void ) {
45. //printf("value is :%d\\n", FibCalc<12>::n);
46. Printer<12>();
47. return 0 ;
48. }

复制代码

编译VS2005已经通过……至于其他未知……