实验六 递归

实验六 递归

实验目的和要求

  1. 学会使用递归的方法来解决问题
  2. 掌握递归程序改为非递归程序的方法

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 写出递归版本的斐波那契数列
  2. 将任务一中的代码改造为非递归版本
  3. 将任务二中的代码进一步简化,消去 goto

实验过程

任务一

设计

由函数 F[n] = F[n-1] + F[n-2] (n > 2, F[0] = 1, F[1] = 1),可知斐波那契数列是递归定义的,即斐波那契数列中的第 n 项(n > 1)是由其前面两项来确定的。根据这个特性不难写出代码。

编码实现

编码实现,通过 C++ 来实现以上分析过程。

测试

斐波那契数列-递归版本

代码符合要求。

任务二

设计

通常,当在一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统需先完成 3 件事:

  1. 将所有的实在参数、返回地址等信息传递给被调用函数保存
  2. 为被调用函数的局部变量分配存储区
  3. 将控制转移到被调函数的人口。

而从被调用函数返回调用函数之前,系统也应完成 3 件工作:

  1. 保存被调函数的计算结果
  2. 释放被调函数的数据区
  3. 依照被调函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时,按照“后调用先返回”的原则,上述函数之间的信息传递和控制转移必须通过“栈”来实现,即系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就为它在栈顶分配一个存储区,每当从一个函数退出时,就释放它的存储区,则当前正运行的函数的数据区必在栈顶。

另外通过资料可知有一种特殊的递归——尾递归,即在函数的最后对自身进行调用。这种调用形式导致其具有特殊的性质:尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用记录,因为调用位置、内部变量等信息都不会再用到了,只要直接用内层函数的调用记录,取代外层函数的调用记录就可以了。因此就不需要进行一系列的压栈、出栈等操作,改为非递归版本时也会简单的多。

通过改造可将代码改为尾递归,进而改造为非递归版本。

编码实现

通过 C++ 进行编写代码。

测试

斐波那契数列-非递归版本

任务三

设计

通过任务二中的代码不难画出程序执行的流程图,从而分析出简化版本。

编码实现

通过 C++ 进行编写代码。

测试

斐波那契数列-非递归改进版本

实验收获

通过本次实验,学会使用递归的方法来解决问题,掌握递归程序改为非递归程序的方法。

递归是程序设计中的一个强有力的工具。其一,有很多数学函数是递归定义的;其二,有的数据结构,如二叉树、广义表等,由于结构本身固有的递归特性,则它们的操作可递归地描述;其三,还有一类问题,虽然问题本身没有明显的递归结构,但用递归求解比迭代求解更简单,如八皇后问题、Hanoi 塔问题等。