没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全20151910042-刘鹏-DSA实验04-递归实验1

20151910042-刘鹏-DSA实验04-递归实验1

需积分: 0 0 下载量 51 浏览量 2022-08-08 20:04:56 上传评论收藏 11.55MB DOCX 举报

温馨提示

试读

30页

五、教材翻译TranslationChapter 4 Recursion ＊第四章递归One way to describe repetition withi

资源详情

资源评论

资源推荐

云南大学数学与统计学院数学系信息与计算科学专业

第 1 页共 30 页

云南大学数学与统计学院

上机实践报告

课程名称：数据结构与算法实验

年级：2015 级

上机实践成绩：

指导教师：陆正福

姓名：刘鹏

上机实践名称：递归实验

学号：20151910042

上机实践日期：2017-05-14

上机实践编号：No.04

组号：

上机实践时间：上午 3、4 节

一、实验目的

1. 熟悉递归算法设计模式

2. 熟悉 Python 递归程序设计

3. 熟悉主讲教材 Chapter 4 的代码片段

二、实验内容

1. 递归有关的数据结构设计与算法设计；

2. 调试主讲教材 Chapter 4 的 Python 程序；

3. （选做）任选一个算法,写出其递归版本与非递归版本,总结不同设计与实现的优缺点。

三、实验平台

Windows 10 1703 Enterprise 中文版；

Python 3.6.0；

Wing IDE Professional 6.0.5-1 集成开发环境。

四、实验记录与实验结果分析

1 题

4.1.1 The Factorial Function（递归函数）

程序代码：

# 4.1.1 The Factorial Function

def factorial(n):

if n == 0:

return 1

else:

return n * factorial(n - 1)

#----------------------------- my main function -----------------------------

print(factorial(10))

程序代码 1

运行结果 1

云南大学数学与统计学院数学系信息与计算科学专业

第 2 页共 30 页

2 题

Drawing an English Ruler

＊画一个英式直尺

程序代码：

# 4.1.2 Drawing an English Ruler

def draw_line(tick_length,tick_label=''):

"""Draw one line with given tick length (followed by optional label)."""

line = '-' * tick_length

if tick_label:

line += ' ' + tick_label

print(line)

def draw_interval(center_length):

"""Draw tick interval based upon a central tick length."""

if center_length > 0: # stop when length drops to 0

draw_interval(center_length - 1) # recursively draw top ticks

draw_line(center_length) # draw center tick

draw_interval(center_length - 1) # recursively draw bottom ticks

def draw_ruler(num_inchs,major_length):

"""Fraw English ruler with given number of inches, major tick length."""

draw_line(major_length,'0') # draw inch 0 line

for j in range(1,1 + num_inchs):

draw_interval(major_length - 1) # draw interior ticks for inch

draw_line(major_length,str(j)) # draw inch j line and label

#------------------------------ my main function ------------------------------

draw_ruler(2,4)

程序代码 2

运行结果 2

云南大学数学与统计学院数学系信息与计算科学专业

第 3 页共 30 页

算法分析：

可以很明显看出，递归就是不断地铺张内存，而循环就不会。一次递归就展开一段内存，当到了最后不满足判断条件，

就开始收敛内存区域。正因如此，流程图也很好画。这个递归具有对称性和深度优先性，因为递归的过程中包含两个完全

一样的子递归，子递归之间有一个画线函数，所以这个函数必然是对称的。

由于数据量不大，所以不需要分析是否是原址递归。其实这个肯定不是原址递归。

云南大学数学与统计学院数学系信息与计算科学专业

第 4 页共 30 页

draw_interval(3)

draw_interval(2)

draw_interval(1)draw_interval(1)