递归(Recurve)的概念迷宫(Maze)问题递归过程与递归工作栈广义表(GeneralLists)递归的概念递归的概念递归的定义若一个对象部分地包含它自递归的定义若一个对象部分地包含它自己己,,或用它自己给自己定义或用它自己给自己定义,,则称这个对则称这个对象是递归的;若一个过程直接地或间接地象是递归的;若一个过程直接地或间接地调用自己调用自己,,则称这个过程是递归的过程。则称这个过程是递归的过程。在以下三种情况下,常常用到递归方法。在以下三种情况下,常常用到递归方法。定义是递归的定义是递归的数据结构是递归的数据结构是递归的问题的解法是递归的问题的解法是递归的定义是递归的定义是递归的求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如,阶乘函数例如,阶乘函数时当时当1,)!1(0,1!nnnnn求解阶乘n!的过程计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}1),2()1(0,1,)(nnFibnFibnnnFib数据结构是递归的数据结构是递归的搜索链表最后一个结点并打印其数值template
voidFind(ListNode*f){if(f→link==NULL)cout<voidPrint(ListNode*f){if(f!=NULL)if(f→data==x)cout<#include"strclass.h”voidHanoi(intn,StringA,StringB,StringC){//解决汉诺塔问题的算法解决汉诺塔问题的算法if(n==1)cout<<"move"<#include#includeclassMaze{private:intMazeSize;intEXIT;Intersection*intsec;public:Maze(char*filename);intTraverseMaze(intCurrentPos);}交通路口结构定义交通路口结构定义structIntersection{intleft;intforward;intright;}Maze::Maze(char*filename){//构造函数:从文件filename中读取各路口//和出口的数据ifstreamfin;fin.open(filename,ios::in|ios::nocreate);//为输入打开文件,文件不存在则打开失败if(!fin){cout<<“迷宫数据文件”<>MazeSize;//输入迷宫路口数intsec=newIntersection[MazeSize+1];//创建迷宫路口数组for(inti=1;i<=MazeSize;i++)fin>>intsec[i].left>>intsec[i].forward>>intsec[i].right;fin>>EXIT;//输入迷宫出口fin.close();}迷宫漫游与求解算法迷宫漫游与求解算法intMaze::TraverseMaze(intCurrentPos){if(CurrentPos>0){//路口从1开始if(CurrentPos==EXIT){//出口处理cout<