一、实验目的
1．掌握递归程序设计的基本原理和方法；
2．熟悉数据结构中顺序表和单链表下的递归算法设计思想；
3．掌握并灵活运用递归算法解决一些较复杂的应用问题。
二、实验环境
1．Windows操作系统的计算机
2．Python3.7环境平台和PyCharm编辑器
三、实验说明
1．实现递归算法的程序设计方法。
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。
3．自主编写程序，必要时参考相关资料。
4．实验学时：2学时
四、实验内容和步骤
1．实验内容
（1） 假设有n个互不相同的数依次入栈出栈，入栈和出栈可以交替进行，问总共可能有多少种不同的出栈序列？
思考提示（但不限于此）：
设n个数入栈共有f(n)种不同的出栈序列。假设这n个数依次为1-n；假设k是第一个出栈的数；比k早进栈且晚出栈的有k-1个数，一共有f(k-1)种出栈序列；比k晚进栈且晚出栈的有n-k个数，一共有f(n-k)种出栈序列。所以一共有f(k-1)*f(n-k)种方案。
当k取不同值时，产生的出栈序列是相互独立的，所以将结果累加。k的取值范围为1至n，所以出栈序列总数f(n)=f(0)*f(n-1)+f(1)*f(n-2) + ... + f(n-1)f(0)。
自己先写出f(n)的递归公式，分为k=0和k>0两种情况考虑，再写代码。
（2）假设L是一个带头结点的单链表，设计递归算法使单链表L逆置。
参考思路：
from LinkList import LinkList,LinkNode
def Reverse(L):
L.head.next=Reverse1(L.head.next,L.head.next)
return L
def Reverse1(t,h):
……
#主程序
a=[ ]
L=LinkList()
L.CreateListR(a)
print()
print(" L: ",end=''),L.display()
print(" 递归逆置")
L=Reverse(L)
print(" L: ",end=''),L.display()2．实验步骤
（1）分析实验内容，写出程序大致框架或完整的程序代码。
（2）进入Python集成环境。
（3）编辑程序并进行保存。
（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。
（5）检查程序输出结果。
五、实验代码与结果（程序运行代码及其结果）
1． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
#递归公式如下：
#当k=0时，f(0)=1
#当k>0时，f(k)=f(0)*f(k-1)+f(1)*f(k-2)+...+f(k-1)*f(0)
def s(n): #定义递归函数S
if n <= 1: #当只有一个元素，则有1个出栈序列
return 1
f = [0]*(n+1)#定义一个长度为n+1的列表f并把所有元素初始化为0
f[0] = 1#把f[0]初始化为1
for i in range(1, n+1):
for j in range(i):
f[i] += f[j]*f[i-j-1]
return f[n]
if __name__ =='__main__':
print(s(7))
2． （1）给出算法的基本设计思想。 （2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
from LinkList import LinkList,LinkNode
def Reverse(self):
if self.head.next is None or self.head.next.next is None: # 当单链表为空或者只有一个节点时无需反转
return self
pre = None #增加指向当前节点前一个节点的指针
p = self.head.next
while p is not None:
q = p.next #记录当前节点的下一个节点
p.next = pre #改变当前节点的指针方向
pre = p #更新前一个节点指针
p = q #当前节点往下移动
self.head.next = pre #更新头结点的指针
return self
if __name__ == '__main__':
a=[1,2,3,4,5]
L=LinkList()
L.CreateListF(a)
print("Original List L: ", end='')
L.display()
print("Reversed List L: ", end='')
head = L.Reverse().head.next
while head != None:
print(str(head.data)+' ', end='')
head = head.next
print()