递归思想与斐波那契数列的优化

菲波那切数列的实现

斐波那切数列：1 1 2 3 5 8 13 21 …

定义：

实现方法一：（简单递归写法）

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>

long Fib(int n)
{
        if (n == 0 || 1 == n)
               return 1;
        else
               return Fib(n - 1) + Fib(n - 2);
}

int main()
{
        int i = 0;
        for (; i <= 5; i++)
        {
               printf("%d ", Fib(i));
        }
        printf("\n");
        system("pause");
        return 0;
}

时间复杂度：递归算法=递归总次数 x 每次递归次数

优化1：尾递归

尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。

尾递归的本质是：将单次计算的结果缓存起来，传递给下次调用，相当于自动累积。

long Fib(long first, long second, int n)
{
        if (n == 0 || 1 == n)
               return 1;
        if (n == 2)
               return first + second;
        return Fib(second, first + second, n - 1);
}

int main()
{
        int i = 0;
        for (; i <= 5; i++)
        {
               printf("%d ", Fib(1,1,i));
        }
        printf("\n");
        system("pause");
        return 0;
}

时间复杂度：O(n)

优化2：非递归循环写法

long Fib(int n)
{
        if (n == 0 || 1 == n)
               return 1;
        else
        {
               long first = 1, second = 1, tmp = 0;
               int i = 2;
               for (; i <= n; ++i)
               {
                       tmp = first + second;
                       first = second;
                       second = tmp;
               }
               return tmp;
        }
}

int main()
{
        int i = 0;
        for (; i <= 5; i++)
        {
               printf("%d ", Fib(i));
        }
        printf("\n");
        system("pause");
        return 0;
}

时间复杂度：O(n)

递归思想

在上面菲波那切数列的实现中我们用到递归的思想，我们说在定义一个过程或者函数时出现调用本过程或本函数的成分，称之为递归。

一般，递归模型是由两部分组成，一是递归出口，给出了递归的终止条件；另一部分为递归体，他确定递归求解时的递归关系。

下图展示的是用递归求斐波那契时的过程：

如何设计递归算法

递归算法的设计方式是：先确定对应的递归模型，再将其转换为对应的递归算法。

其核心思想是把问题简化分为几个子问题，其中子问题的形式与算法与原问题算法相似。

例子：若s是n个元素的集合，则s的幂集p(s)定义为所有子集的集合。例如：s={a,b,c}，则p(s) = {{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。给定s，设计一个递归算法求p(s).

解： 求p(s)递归算法如下：

void CreatePset(ps, s)
{
        if (s未扫描完)
        {
               向幂集ps中的每个集合中插入s的当前元素构成ps1;
               将幂集ps和幂集ps1合并成幂集ps;
               CreatePset(ps, s中的下一个元素);
        }
}

例子2：设计一个递归算法求一个数组中所有元素之和

解：设f(i)为数组中所有元素之和，则 f(i) = arr[0] + arr[1] + … +arr[i-1]，假设我们已经知道 f(i-1)的值，则 f(i) = f(i-1) + arr[i-1]

相应算法：

int fun(int arr[], int i)
{
        if (i == 1)
               return arr[0];
        else
               return (fun(arr, i - 1) + arr[i - 1]);
}