记忆化递归例题——斐波那契数列

迈不过友情╰ 2023-02-28 04:27 23阅读 0赞

### 文章目录 ###

*  记忆化递归讲解
 *   *  递归
     *  比如利用递归求斐波那契数列的第N项值
     *  试试输入100结果是什么
     *   *  几分钟后
     *  斐波那契数列的哈夫曼树图
     *  记忆化方法
     *   *  创建数组，将其值全部为0
         *  构建函数框架
         *  写入代码
 *  结束语
 *   *  总结
     *  下期预告

# 记忆化递归讲解 #

## 递归 ##

递归有尾递归，中间递归和多重递归，如果递归次数超两次（包括两次）那么递归时就有可能重复递归，使程序变慢

## 比如利用递归求斐波那契数列的第N项值 ##

#include<iostream>
    using namespace std;
    int op(int n)
    { 
    	if(n==1||n==2) return 1;
    	return op(n-1)+op(n-2);
    }
    int main()
    { 
    	int n;
    	cin>>n;
    	cout<<op(n);
    	return 0;
    }

这是用尾递归求斐波那契数列的第N项

## 试试输入100结果是什么 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center]  
没报错，也没输出结果……  
这说明程序还在运行……

### 几分钟后 ###

出来了  
显然，这是程序在运行，但是运行太慢，对于一些严格要求速度的题目来说，这是“运行超时”  
怎么说呢，来看看斐波那契数列的哈夫曼树图

## 斐波那契数列的哈夫曼树图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70]

显然，子节点fib(2)被重复执行了5次，加上调用函数时要保留上下文，空间消耗了不少，动态规划是怎样解决斐波那契数列的呢

## 记忆化方法 ##

将3的值保存，当再次计算到该项时返回该值，于是，这次递归结束，继续往下递归  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center 1]  
那么用代码怎么解决呢

### 创建数组，将其值全部为0 ###

创建一个全局变量的数组，有N个元素，每次将n的值传进数组中，当再一次计算n时直接返回a\[n\]

#include<iostream>
    using namespace std;
    int a[101];//假设n不超过100
    int main()
    { 
        int n;
        cin>>n;
        return 0;
    }

### 构建函数框架 ###

#include<iostream>
    using namespace std;
    int a[101];//假设n不超过100
    int fib(int n)
    { 
        //TODO
    }
    int main()
    { 
        int n;
        cin>>n;
        cout<<fib(n);
        return 0;
    }

### 写入代码 ###

#include<iostream>
    using namespace std;
    int a[101]={ 0};//这里将数组a全部赋值为0 
    int fib(int n)
    { 
    	if(n==1||n==2)
    	{ 
    		a[n]=1;
    		return 1;
    	}
    	if(a[n]!=0) return a[n];//如果重复递归直接返回 
    	else
    	{ 
    		//没有重复将a[n]赋值
    		a[n]=fib(n-1)+fib(n-2); 
    		return a[n];
    	}
    }
    int main()
    { 
        int n;
        cin>>n;
        cout<<fib(n);
        return 0;
    }

# 结束语 #

## 总结 ##

程序到此完毕，当我们再次输入100时已经可以立刻出来了，一个负数，是因为越界，但是总比等待几分钟后输出来值要好  
试试在程序还未加入记忆化算法时输入50是多少，那么现在输入50呢？

## 下期预告 ##

算法：无，等待ing  
**备注：**  
快速幂不写了，算法真的没梗了  
I 'm learning now. Please keep quiet!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/562e25095edd48dd8a7d86276cda5329.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70]: /images/20230209/4fd7758824b84790a80572261598fa82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230209/e85327d844944508a9884e69d127b4b4.png