论坛 › 游戏编程综合讨论区 › 递归(已解决)

august 发表于 2007-9-26 13:52:53

递归(已解决)

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

secondsen 发表于 2007-9-26 14:11:01

这个东西。。。

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

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

突然下定决心要学C++

august 发表于 2007-9-26 14:15:06

这样的话就不叫递归吧.......

shawind 发表于 2007-9-26 14:18:14

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

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

august 发表于 2007-9-26 15:08:26

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

august 发表于 2007-9-26 15:20:02

#include<stdio.h>

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

secondsen 发表于 2007-9-26 17:39:57

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

不懂的我不再这丢人了。。。。

rednaxela 发表于 2007-9-26 20:08:37

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

对应LZ的递归算法,应该这样才对:
/*
* fib.c
* 简单递归fibonacci数列算法演示
*/
#include <stdio.h>

int array = { 0, 1 };

int fib(int x) {
    switch (x) {
    case 0:
      return 0;
    case 1:
      return 1;
    default:
      array = fib( x - 1 ) + fib( x - 2 );
      return array;
      /* basically you should just return the result
          instead of assigning the value into the array
          return fib( x - 1 ) + fib( x - 2 ); */
    }
}

void main() {
    int i;

    fib( 5 );
    for ( i = 0; i < 5; ++i ) {
      printf("%d ", array);
    }
}

但实际上这么做效率很低,估计LZ只需要这样就行了:
/*
* fib.c
* 简单循环fibonacci数列算法演示
*/
#include <stdio.h>

int array = { 0, 1 };

void fib(int x) {
    int i;

    for ( i = 2; i < x; ++i ) {
      array[ i ] = array[ i - 1] + array[ i - 2];
    }
}

void main() {
    int i;

    fib( 5 );
    for ( i = 0; i < 5; ++i ) {
      printf("%d ", array);
    }
}

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

rednaxela 发表于 2007-10-19 12:35:33

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

lw 发表于 2007-10-19 20:14:53

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



template<int f>
class FibCalc {
public:
    enum {
      n = FibCalc<f-2>::n + FibCalc<f-1>::n,
    };
};

template<>
class FibCalc<0> {
public:
    enum {
      n = 0,
    };
};

template<>
class FibCalc<1> {
public:
    enum {
      n = 1,
    };
};

// ---------------

#include <stdio.h>
template<int count>
class Printer : private FibCalc<count> {
public:
    Printer(void) { Printer<count-1>(); printf("%d ", n); }
};

template<>
class Printer<0> : private FibCalc<0> {
public:
    Printer(void) { printf("%d ", n); }
};

// ---------------

int main( void ) {
//printf("value is :%d\\n", FibCalc<12>::n);
Printer<12>();
return 0 ;
}


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

查看完整版本: 递归(已解决)