词条 | 递归调用 |
释义 | 递归调用是一种特殊的嵌套调用,是某个函数调用自己,而不是另外一个函数。递归调用一种解决方案,一种是逻辑思想,将一个大工作分为逐渐减小的小工作,比如说一个和尚要搬50块石头,他想,只要先搬走49块,那剩下的一块就能搬完了,然后考虑那49块,只要先搬走48块,那剩下的一块就能搬完了……,递归是一种思想,只不过在程序中,就是依靠函数嵌套这个特性来实现了。 基本信息定义递归调用就是在当前的函数中呼叫当前的函数并传给相应的参数,这是一个动作,这一动作是层层进行的,直到满足一般情况的的时候,才停止递归调用,开始从最后一个递归调用返回。 英文recursive invocation 函数模型fun(形参){ fun(参数值1) //第一次递归调用 fun(参数值2) //第二次递归调用 递归举例C语言中的递归计算阶乘的代码 long fact(long n) { if(n==0||n==1) return 1L; else return n*fact(n-1); } 这个函数叫做fact,它自己调用自己,这个就是一个典型的递归调用,调用过程类似一个栈。 注: 主调函数又是被调函数。执行递归函数将反复调用其自身。 每调用一次就进入新的一层。 int f (int x) { int y; z=f(y); return z; } 这个函数是一个递归函数。 但是运行该函数将无休止地调用其自身,这当然是不正确的。为了防止递归调用无终止地进行, 必须在函数内有终止递归调用的手段。常用的办法是加条件判断, 满足某种条件后就不再作递归调用,然后逐层返回。 下面举例说明递归调用的执行过程。 Pascal中的递归const z=10000; var a:array[0..z+1]of integer; n,j,i,k:longint; begin readln(n);write(n,'!='); begin a[1]:=1; for i:=1 to n do begin for j:=1 to z do a[j]:=a[j]*i; for k:=1 to z do begin a[k+1]:=a[k+1]+a[k]div 10; a[k]:=a[k]mod 10; end; end; i:=z;k:=0; repeat if a[i]<>0 then k:=1; i:=i-1; until k=1; k:=0; for j:=i+1 downto 1 do write(a[j]); end; writeln; end. c++语言中的递归#include<iostream> using namespace std; int fac(int n) { int s=1; for (int i=n;i>0;i--) { if (s<=s*i) s=s*i; else { cout<<"over int area"<<endl; return 0; }; } return s; } void main() JAVA写的递归调用public class TestDg { public static void main(String[] args) { System.out.println(method(5)); } public static int method(int n) { if (n == 1) return 1; else return n * method(n - 1); } } 汉诺塔------软件递归调用里面最经典的一个案例 #include<stdio.h> int c=0; /* 全局变量,搬动次数 */ void move(char x,int n,char z) { /* 第n个圆盘从塔座x搬到塔座z */ printf("第%i步: 将%i号盘从%c移到%c\",++c,n,x,z); } void hanoi(int n,char x,char y,char z) { /* 将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘 */ /* 按规则搬到塔座z上。y可用作辅助塔座 */ if(n==1) move(x,1,z); /* 将编号为1的圆盘从x移到z */ else { hanoi(n-1,x,z,y); /* 将x上编号为1至n-1的圆盘移到y,z作辅助塔 */ move(x,n,z); /* 将编号为n的圆盘从x移到z */ hanoi(n-1,y,x,z); /* 将y上编号为1至n-1的圆盘移到z,x作辅助塔 */ } } void main() { int n; printf("3个塔座为a、b、c,圆盘最初在a座,借助b座移到c座。请输入圆盘数:"); scanf("%d",&n); hanoi(n,'a','b','c'); } 递归详解调用前一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统需要完成3件事情: (1)将所有的实参、返回地址等信息传递给被调用函数保存; (2)为被调用函数的局部变量分配存储区; (3)将控制转移到被调函数的入口。 调用中而从被调用函数返回调用函数之前,系统也应完成3件工作: (1)保存被调函数的计算结果; (2)释放被调函数的数据区; (3)依照被调函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时,按照后调用先返回的原则。 递归函数的特点所有递归函数的结构都是类似的。 (1)函数要直接或间接调用自身。 (2)要有递归终止条件检查,即递归终止的条件被满足后,则不再调用自身函数。 (3)如果不满足递归终止的条件,则调用涉及递归调用的表达式。在调用函数自身时,有关终止条件的参数要发生变化,而且需向递归终止的方向变化。 总结函数的调用原则和数据结构栈的实现是相一致。也说明函数调用是通过栈实现的。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。