动态规划变形算法在递归函数中的应用

封震震

摘要：能够编写递归函数必须具备两个条件，一个是递归方程，另一个是边界条件，动态规划算法具有最优子结构和重叠子问题两个性质，动态规划思想的引入可以降低递归函数的运行时间，也就是减少了计算所有小于或等于给定参数的递归调用所要求的时间，其中仅仅处理一次递归调用的时间，避免重复问题重复计算。以斐波那契数列为例，通过编程对照动态规划变形算法在递归函数的应用。

关键词：动态规划;递归调用;时间复杂度

中图分类号：TP311        文献标识码：A        文章编号：1009-3044（2019）03-0067-02

1 一般递归函数定义格式

递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。层数越多重复计算量就越大，递归有两个要素，递归方程和边界条件。当函数一直递归调用，直到遇到边界条件后返回。斐波那契数列递归函数的两个要素如下。

2 递归函数改进前后比较

2）改进后，定义一个函数Fib（long  a[]，int n），具有两个参数，形参a[]表示斐波那契数列，形参n表示第几个数列，a[]数组具有备忘功能的自顶向下存值，当要引用某一个值时，判定是否计算过，若已经计算，直接赋值即可。若n=6时，改进后，递归处理的过程如图3所示，其计算效率很高。

3 结束语

动态规划变形算法（备忘录方法）与动态规划算法是有不同点，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的，但两者在处理重复性問题时的思路是一样，避免重复计算。使用动态规划变形算法可弥补递归调用的缺点：1）分配空间及调用次数倍数减少。递归是函数调用自身，在程序中函数调用是有时间和空间的消耗的，进行每一次函数调用时，都需要在内存栈中分配空间来保存参数、返回地址以及临时变量。2）避免重复计算问题。递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算。3）不会超出栈的容量。调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。

函数具有时间复杂度和空间复杂度，尤其时间复杂度是函数的重要指标，当我们编写程序的时候一定要考虑其效率，尽可能应用相关的算法提高函数的性能。

参考文献：

[1] 陈晓梅，张晶.动态规划算法的教学探讨[J].电脑知识与技术，2018，14（26）：146-147.

[2] 吕丹，杨子寒，周君.动态规划算法在生活中的应用[J].电脑知识与技术，2018，14（17）.

[3] 李从宏.基于递归调用技术的关键字搜索软件设计[J].电脑编程技巧与维护，2018（12）.

[4] 刘卓亚.基于C语言的递归算法研究[J].数字技术与应用，2018，36（3）：132-133.

[5] 张玮.动态规划法求解最大连续子序列和问题[J].电子技术与软件工程，2018（20）：122.

【通联编辑：朱宝贵】