Python Programming: An Introduction to Computer Science

230 CHAPTER13. ALGORITHMANALYSISANDDESIGN

1. Thereareoneormorebasecasesforwhichnorecursionis required.


2. Whenthedefinitionis recursivelyapplied,it is alwaysappliedtoa smallercase.


3. Allchainsofrecursioneventuallyendupat oneofthebasecases.

13.2.2 Recursive Functions

Youalreadyknow thatthefactorialcanbecomputedusinga loopwithanaccumulator. Thatimplementation
hasa naturalcorrespondencetotheoriginaldefinitionoffactorial. Canwealsoimplementa versionof
factorialthatfollowstherecursive definition?
If wewritefactorialasa separatefunction,therecursive definitiontranslatesdirectlyintocode.

def fact(n):
if n == 0:
return 1L
else:
return n * fact(n-1)

Doyouseehowthedefinitionthatreferstoitselfturnsintoa functionthatcallsitself? Thefunctionfirst
checkstoseeif weareata thebasecasen == 0and,if so,returns1 (notetheuseofa longintconstant
sincefactorialsgrow rapidly).If wearenotyetat thebasecase,thefunctionreturnstheresultofmultiplying
nbythefactorialofn-1. Thelatteris calculatedbya recursive calltofact(n-1).
I thinkyouwillagreethatthisis a reasonabletranslationoftherecursive definition.Thereallycoolpart
is thatit actuallyworks!We canusethisrecursive functiontocomputefactorialvalues.

from recfact importfact
fact(4)
24
fact(10)
3628800

Somebeginningprogrammersaresurprisedbythisresult,butit followsnaturallyfromthesemanticsfor
functionsthatwediscussedwaybackinChapter6.Rememberthateachcalltoa functionstartsthatfunction
anew. Thatmeansit getsitsowncopy ofany localvalues,includingthevaluesoftheparameters.Figure13.1
showsthesequenceofrecursive callsthatcomputes2!.Noteespeciallyhow eachreturnvalueis multiplied
bya valueofnappropriateforeachfunctioninvocation.Thevaluesofnarestoredonthewaydownthe
chainandthenusedonthewaybackupasthefunctioncallsreturn.

fact(2) n = 1

1

n = 0 1

2

n = 2

def fact(n):

if n == 0:

return 1

else:

return n * fact(n−1)

n:

def fact(n):

if n == 0:

return 1

else:

return n * fact(n−1)

2 n: 1

def fact(n):

if n == 0:

return 1

else:

return n * fact(n−1)

n: 0

Figure13.1:Recursive computationof2!

13.2.3 Recursive Search.

Now thatwehave a techniqueforimplementingrecursive definitions,wearereadyto gobackandlookagain
atbinarysearchasa recursive process.Thebasicideawastolookatthemiddlevalueandthenrecursively
searcheitherthelowerhalfortheupperhalfofthearray. Thebasecasesfortherecursionaretheconditions
whenwecanstop,namelywhenthetargetvalueis found,orwerunoutofplacestolook.Therecursive calls