章递归内容要点简介函数调用与关系什么大二上ch05 recursion.pptx

下载文档

0
0
约8.06千字
约 29页
2024-08-12 发布于北京
举报
版权申诉
保障服务

章递归内容要点简介函数调用与关系什么大二上ch05 recursion.pptx

1、本文档共29页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

Chapter5Recursion

ContentsPointsIntroductiontoRecursionRelationofFunction-callandRecursion.WhatisRecursion?Factorials:ARecursiveDefinitionDivideandConquer:TheTowersofHanoiPrinciplesofRecursionDesigningRecursiveAlgorithmsHowRecursionworksTailRecursion

RelationofFunction-callandRecursionWhatmustbedonewhenfunction-callhappened?theplacewherethecallwasmade（调用点－返回地址）allthelocalvariables,processorregistersandlike（局部变量、寄存器等）Invocationrecord（调用记录）activationrecord（激活记录）Property:LastIn,FirstOut（LIFO）（后进先出）

RelationofFunction-callandRecursion

WhatisRecursion?intfun(intn){ if(n=1) returnn; returnn*fun(n-1);}intfun1(intn){ if(n=1) returnn; return(fun2(n));}intfun2(intn){ return(n*fun1(n-1));}Recursionisthenameforthecasewhenafunctioninvokesitself（直接递归）invokesasequenceofotherfunction,oneofwhicheventuallyinvokesthefirstfunctionagain（间接递归）

Factorials:ARecursiveDefinition4!=4×3!=4×(3×2!)=4×（3×（2×1！））=4×（3×（2×（1×0!）））=4×（3×（2×（1×1）））=4×（3×（2×1））=4×（3×2）=4×6=24

Factorials:ARecursiveDefinitionEveryrecursiveprocessconsistsoftwoparts:Asmallest,basecasethatisprocessedwithoutrecursion;（非递归部分）Ageneralmethodthatreducesaparticularcasetooneormoreofthesmallercases,therebymakingprogresstowardeventuallyreducingtheproblemallthewaytothebasecase.（递归部分）Programmersmustlookatthebigpictureandleavethedetailedcomputationstothecomputer.

Factorials:ARecursiveDefinitionintfactorial(intn){ if(n==0) return1; returnn*factorial(n-1);}Recursionprogram

DivideandConquer:TheTowersofHanoiTheProblemmove(64,1,3,2)——move64disksfromtower1totower3usingtower2astemporarystorage.Onediskcanbemovedatatimeandnodiskiseverallowedtobeplacedontopofasmallerdisk.

DivideandConquer:TheTowersofHanoiTheSolutionConcentrateourattentionnotonthefirststep,butrather