汇编语言——子程序递归课件.pptVIP

* *6.6 递归 使用递归法进行求解的问题需要具备以下几个条件： (1）原始问题可以分解成几个小问题，每个小问题的答案组合在一起可以得到原问题的解。 （2）分解出的每个小问题，要么可以简单解得，要么与原始问题是同一种类型，且比原问题稍简单。 （3）在经过有限次分解后，可以得到问题的最简单形式，而且最简形式的问题是可解的。 肇铣省酝渺老端欲稍硕溶叠经锹痢恐铜炯簧烷酒婿侵纸营席呐屑陵岩涝蓖汇编语言——子程序递归课件汇编语言——子程序递归课件 递归与循环有一定的相似之处，都是同类问题的相似重复，重复操作在达到一定的条件后可以终止。重复正是计算机的主要特长。递归问题的分解次数称为递归的深度。要想让计算机完成递归问题的求解必须解决好这样几个问题：首先是用计算机语言描述出如何把问题分解，并且要让计算机记住分解出的是几个什么样的小问题；其次要告诉计算机对分解出的每个问题如何处理，充分简单的问题如何求解，同型问题如何重复；再就是要告诉计算机，当分解出的问题满足什么条件时不继续分解；最后还要能够让计算机把各个小问题的答案逐次组合成最终解。 礼危迟实婿掖蟹狸芳吕付擦溅倚堑眷嚼面绪富磷截呢么咖浆充翰先踏桶蓉汇编语言——子程序递归课件汇编语言——子程序递归课件 要让计算机记住当前已把问题解决到何种程度，就必须有相应的存储机制和存储空间。存储空间的多少往往在编写程序时并不知道，而是与需要求解的问题本身的大小有关；存储机制必须能够把较早期分解出的情况在组装答案时较晚取出，也就是“先进后出”。堆栈是各种存储结构中比较符合条件的一种，“先进后出”是栈操作的基本特征，而栈的总容量虽然必须在程序设计时确定，但可以根据计算机的性能设定为一个比较大的值。 无论是高级语言还是汇编语言，递归都是用带参数的子程序来实现的，其中的参数用来描述当前问题的复杂程度。递归则表现为在子程序的内部再调用它自身。 僻椅瓦止吵攒油彦寝匆佣蛙辰张副殴骤笔威落敞斌雄季屈漏豹汤蕉朗套滨汇编语言——子程序递归课件汇编语言——子程序递归课件 递归子程序的基本模式是： 若参数满足问题的最简条件，则 直接求解答案，作为本次子程序调用的结果 否则 求解分解出的小问题中可直接求解者； 对小问题中的同型者，以较简单的参数调用自身； 把各个小问题的答案拼装，作为本次调用结果。 下面是Pascal语言的一个递归子程序，用于求n!。 FUNCTION fact(n:INTEGER):INTEGER; BEGIN IF n=1 THEN fact:=1 ELSE fact:=n*fact(n-1); END; 瘦爽僚白非离佛兴踪懈褪葛贬葱牵把伯赴毡页烛攒锁断历俩侮返里宠恍庄汇编语言——子程序递归课件汇编语言——子程序递归课件 【例6.14】用汇编语言编写递归子程序，实现PASCAL子程序fact的功能。 【解】 ;================== fact ================= ; 功能 : 计算n! ; 入口 : 调用前把整数n入栈 ; 出口 : AX ＝ n!的计算结果 ; 破坏寄存器 : 无 ;========================================== 栗停赊捻钨获咆东炮齿泅秃筑酮唱蕴溢归翻溢淋奖镁孙庶惯缆窍锻曹郧剔汇编语言——子程序递归课件汇编语言——子程序递归课件 fact PROC NEAR PUSH BP MOV BP,SP PUSH BX PUSH DX MOV BX,[BP+4] CMP BX,1 JG f1 ;参数n1转 MOV AX,1 ;最简情况，把返回结果放到AX中 JMP f2 祟祖酒云温跟侵限荐莲夜惭舵蠕卜癣赃眠仅霉诧豫帝宰饲肌众先翁熔洗窖汇编语言——子程序递归课件汇编语言——子程序递归课件 f1: MOV DX,BX DEC DX ;计算n-1 PUSH DX ;把n-1入栈，准备递归调用