模拟的递归实验报告

.

数据结构 递归的模拟实验报告

专业班级：软件工程13—1

姓名：罗云臻 学号：2013214368 日期：2014/10/10

一、实验目的和要求

实验目的：

了解递归算法在计算机中对数据的存储和处理方式，并能够将递归算法改成非递归算法

实验要求：将指定的一个递归函数改成非递归函数 二、实验环境

(联想G480)

CPU: Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz 2.60GHz 操作系统： Windows7 64位操作系统 RAM: 4GB（3.85GB可用） IDE集成开发环境： code::blocks 13.12

三、实验内容

用goto语句以及循环语句两种方法模拟下面所示的递归函数： void P(int N) {

If( N>0) {

P(N-1); cout<

.

.

并证明下面有关程序功能描述的正确性

(1)在调用P（N）所产生的输出序列中，当且仅当序号为基数时，输出项的值为1； (2)在调用P（N）所产生的输出序列中，输出2的项数为2^(n-2)。

四、实验过程

4.1 任务定义和问题分析

（1）在模拟递归之前，应先画出递归运行的模拟图，才方便分析递归的运行状态；

（2）熟练掌握递归模拟的转换规则并根据转换规则将递归转化为非递归； （3）模拟递归所采用的存储结构——栈；

4.2 数据结构的选择和概要设计

先根据转换规则将递归函数改写为以goto语句实现递归部分的新函数，在通过对新函数的逻辑分析画出程序流程图，最后根据程序流程图改为只用栈和循环结构模拟的递归程序。

.

.

4.3 详细设计

根据转换规则将函数递归部分用goto语句改成非递归： void P(int N) { If( N>0) { P(N-1); cout<0){} L0: if(N>0) { s.push(N); N= N-1; goto L0; } L1: cout<