发现递归算法求第n位数的效率问题

Question

1,1，2,3,5,8,13,21,34,55求第30位
我将网上普遍存在的代码和我写的代码都写进去了，直接复制可以编译，
我是个CSharp新手，贴出来这个帖子只为共同学习using System;class program
{
    static void Main()
    {
        Console.WriteLine("已知数字序列：1,1,2,3,5,8,13,21,34,55....。求第N位？");
        Console.WriteLine("当数字大于33时效率问题就表现的明显了，建议不要超过38：");
        while (true)
        {
            Console.Write("请输入想要的第几位数字的编号：");
            int i = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("我的结果：" + add(1, 1, i));
            Console.WriteLine("网上结果：" + fun(i) + "\n");
        }
    }
    /// <summary>
    /// 这个是反推（网上普遍）
    /// </summary>
    /// <param name="n"></param>
    /// <returns>返回第n位数字</returns>
    static int fun(int n)
    {
        if (n == 1 || n == 2)
            return 1;
        else
            return fun(n - 1) + fun(n - 2);
    }
    /// <summary>
    ///这个是正推；
    /// </summary>
    /// <param name="a">第一个数字，一般为1</param>
    /// <param name="b">第二个数字，一般也为1</param>
    /// <param name="i">数字编号</param>
    /// <returns>返回第i位数字</returns>
    static int add(int a, int b, int i)
    {
        if (i > 3)
            return add(b, a + b, i - 1);
        else if (i == 3)
            return a + b;
        else if (i == 2)
            return b;
        else if (i == 1)
            return a;
        else
            return 0;
    }
}

Answer 1

斐波那契static int Fibonacci(int index)
{
  return index <= 2 ? 1 : Fibonacci(index - 1) + Fibonacci(index - 2);
}
public static Func<int, int> Fibonacci = n => n > 1 ? Fibonacci(n - 1) + Fibonacci(n - 2) : n;

Answer 2

非递归        public static Int32 Fibonacci(Int32 n)
        {
            if (n == 1 || n == 2)
                return 1;            Int32 a = 1;
            Int32 b = 1;
            Int32 c = 0;
            Int32 i = 3;
            for (Int32 j = i; j <= n; j++)
            {
                c = a + b;
                a = b;
                b = c;
            }            return c;        }

Answer 3

http://topic.csdn.net/u/20091015/21/c30da67b-7346-4552-b2e2-11d620d5e366.html

Answer 4

非递归的方法简单的很，递归算法把int 型改成long的话能算到第92位，7540113804746346429

Answer 5

相比之下， static int add(int a, int b, int i)
    {
        if (i > 3)
            return add(b, a + b, i - 1);
        else if (i == 3)
            return a + b;
        else if (i == 2)
            return b;
        else if (i == 1)
            return a;
        else
            return 0;
    }每次只调用自身一次，效率就要明显降低，

Answer 6

逍遥兄......其实递归慢的原因是，每执行一次只能+1，如果算出的结果是10000000，就要执行10000000次。
所以递归的复杂度是1.618^n，而累加递推的话，复杂度是O(n)，当然还有log(n)的方法，但是算1000以内都有点大材小用了。

Answer 7

ls的1.618哪来的？递归的复杂度你怎么算的？时间复杂度还是空间复杂度？时间频度
　　一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。递归和循环的调用次数是一样的，所以都是O(n)。
你说每次只执行一次加法，这个没错。关键是堆栈的创建，创建堆栈需要分配内存，创建参数，压入堆栈，这个操作不慢，但多了的话，影响就明显了。

Answer 8

逍遥兄，我说的递归的复杂度是特指这个问题的，指的是时间复杂度，斐波那契数列相邻项的比值近似看成(Sqrt(5) + 1)/2，约等于1.618，求第n项，用这个递归的话，复杂度就是O(1.618^n)，至于用递归的空间复杂度，是O(n)的。而用循环递推的话，复杂度就低多了，是O(n)的，空间可以做成O(1)的。虽然一般来讲，循环要比递归快一些，但没有这么明显的差距，算第100项，递推用ulong一秒之内算完，递归没个1天算不出来。