课件-第3章附加节递归

栈和队3栈和队3.3用举例迷宫求栈的应用：递给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个定义是递归n!

当n0n(n

当n1longFactorial(longn){if(n==0)returnelsereturnn*Factorial(n-}求解阶n的过main:参数 计算 返回递 结归 参数 计算 返回 果调 返用 参数 计算 返回 回参数 计算 返回参数 直接定值= 返回数据结构是递归fftemplate<classvoidPrint(ListNode<E>*f){if(f->next==NULL)cout<<f->data<<elsePrint(f-}a4 template<classvoidPrint(ListNode<E>*f,Evalue){if(f!=NULL)if(f->data==cout<<f->data<<endl;elsePrint(f->next,value);}递归找含xfffffx问题的解法是递归例，汉诺塔(TowerofHanoi)问题的解法：n1，则将这一个盘子直接从A柱移到C柱上。否则，执行以下三步：C柱做过渡，将A(n-1)个盘子移到B柱上：将AC用AB(n-1)个盘子移到C柱上。#includevoidHanoi(intn,charA,charB,charC)//if(n==1)cout<<"move"<<A<<"to<<C<<else{Hanoi(n-1,A,C,cout<<"move"<<A<<"to"<<<<Hanoi(n-1,B,A,}}A-A-

A-

A-A-

C-

B-B-

A-—分而治之策略（分治法构成递归的条Procedure<name>(<parameterlist>)if(<initialcondition>) return(initialvalue); //return(<name>(parameterexchange}递归过程与递归工作递归调 (n- (n- 返回次

longFactorial(longn){inttemp;if(n==0)returnelsetemp=n*Factorial(n-return}voidmain(){intn;n=}递归工作参参框函数递归时的活动记调用函数

<下一条指令Function(<参数表返回地址返回地址(下一条指令参计算Fact时活动记录的内4//参数返回值4//return36return//22return//36return//22return//11return//01return//递归过程改为非递归过递归过程简洁、易编、易递归过程效率低，重复计算改为非递归过程的目的是提高效这时不必返回后计算斐波那契数列的函数Fib(n)的定(n)

nFib(n1)

nF00,F11,F21,F32,F43,F5求解斐波那契数列的递归算longFib(longn)if(n<=1)returnelsereturnFib(n-1)+Fib(n-}

调用次 NumCall(k)=2*Fib(k+1)-单向递归用迭代法实longFibIter(longn){if(n<=1)returnn;longtwoback=0, oneback=1, for(inti=2;i<=n;i++){Current=twoback+twoback= oneback=}return}尾递归用迭代法实voidrecfunc(intA[], intn){if(n>=0){cout<<A[n]<<“”;recfunc(A,}}voidsterfunc(intA[],intn)while(n>=0){cout<< "<<A[n]<<n--}}递归与回n皇后问nn列的国际象棋棋盘上，若两个皇则称为它们为互相攻击。n皇后问题是指找到这n个皇后的互不攻击的布局。 2#4#1#5#k=n+i-j-0123

0#

1#3#5#0#2#6#解题思安放i行0n-1j0,n-1在j列其它皇后，则出现攻击，撤消在第j列j列安放的皇后不动，递归安放第i+1行皇后。4 col[n]：col[i]i列是否安放了 md[2n-1]md[kk条主对角线 sd[2n-1sd[kk条次对角线是q[nq[iivoidQueen(inti)for(intj=0;j<n;j++)if(ij列没有攻击)ij列安放皇后if(in-1输出一个布局elseij列的皇后}}}voidQueen(inti)for(intj=0;j<n;j++)if(!col[j]&&!md[n+i-j-1]&&{/*ijcol[j]=md[n+i-j-1]=sd[i+j]=q[i]=/*ij列安放皇后if(in-1) /*输出一个布局for(intk=0;k<n;cout<<k<<q[k]<<‘,’;cout<<endl;}elsecol[j]=md[n+i-j-1]=sd[i+j]=0;q[i]=0; /*ij列的皇后*/}}}4532迷宫问45321(入口1(入口234(堵死3(堵死5(堵死 回 退到 右拐弯 左拐弯进到(出口

左直右小行行行型宫型数000700数0007007据交通路口结构定交通路口结构定structIntersection{intleft;intforward;intright;}#include<iostream.h>#include<fstream.h>#include<stdlib.h>classMaze{intMazeSize;intEXIT;Intersection*intsec;Maze(charintTraverseMaze(int}Maze::Maze(char*filename)//filenameifstreamfin;fin.open(filename,ios::in|if(!fin){cerr迷宫数据文件<<<<“打不开”<<}fin>> intsec=new//for(inti=1;i<=MazeSize;fin>>intsec[i].left>>>>fin>> //}迷宫漫游与求解算intMaze::TraverseMaze(intCurrentPos)if(CurrentPos0) //1if(CurrentPos==EXIT){ cout<<C