13.2. RECURSIVEPROBLEM-SOLVING 229
Algorithm: binarySearch-- search for x in range nums[low] to nums[high]
mid = (low + high)/ 2
if low > high
x is not in nums
elif x < nums[mid]
perform binarysearch for x in range nums[low] to nums[mid-1]
else
perform binarysearch for x in range nums[mid+1] to nums[high]
Ratherthanusinga loop,thisdefintionofthebinarysearchseemstorefertoitself.Whatis goingonhere?
Canweactuallymake senseofsucha thing?
13.2.1 Recursive Definitions.
Adescriptionofsomethingthatreferstoitselfis calledarecursivedefinition.Inourlastformulation,the
binarysearchalgorithmmakesuseofitsowndescription.A“call”tobinarysearch“recurs”insideofthe
definition—hence,thelabelrecursive definition.
Atfirstglance,youmightthinkrecursive definitionsarejustnonsense. Surelyyouhave hada teacher
whoinsistedthatyoucan’t usea wordinsideofitsowndefinition?That’s calleda circulardefinitionandis
usuallynotworthmuchcreditonanexam.
Inmathematics,however, certainrecursive definitionsareusedallthetime.Aslongasweexcercisesome
careintheformulationanduseofrecursive definitions,they canbequitehandyandsurprisinglypowerful.
Let’s lookat a simpleexampletogainsomeinsightandthenapplythoseideastobinarysearch.
Theclassicrecursive exampleinmathematicsis thedefinitionoffactorial.BackinChapter3, wedefined
thefactorialofa valuelike this:
n! n
n 1
n 2
1 Forexample,wecancompute
5! 5
4
3
2
1 Recallthatweimplementeda programto computefactorialsusinga simpleloopthataccumulatesthefactorial
product.
Lookingat thecalculationof5!,youwillnoticesomethinginteresting.If weremove the5 fromthefront,
whatremainsis a calculationof4!.Ingeneral,n! n
n 1 !. Infact,thisrelationgivesusanotherwayof
expressingwhatis meantbyfactorialingeneral.Hereis a recursive definition:
n!
1 ifn 0
n
n 1 ! otherwiseThisdefinitionsaysthatthefactorialof0 is,bydefinition,1, whilethefactorialofany othernumberis defined
tobethatnumbertimesthefactorialofonelessthanthatnumber.
Eventhoughthisdefinitionis recursive,it is notcircular. Infact,it providesa verysimplemethodof
calculatinga factorial.Considerthevalueof4!.Bydefinitionwehave
4! 4
4 1 ! 4
3!Butwhatis 3!?To findout,weapplythedefinitionagain.
4! 4
3! 4
3
3 1 ! 4
3
2!Now, ofcourse,wehave toexpand2!,whichrequires1!,whichrequires0!.Since0!is simply1,that’s the
endofit.
4! 4
3! 4
3
2! 4
3
2
1! 4
3
2
1
0! 4
3
2
1 1 24
Youcanseethattherecursive definitionis notcircularbecauseeachapplicationcausesustorequestthe
factorialofa smallernumber. Eventuallywegetdownto0,whichdoesn’t requireanotherapplicationofthe
definition.Thisiscalledabasecasefortherecursion. Whentherecursionbottomsout,wegeta closed
expressionthatcanbedirectlycomputed.Allgoodrecursive definitionshave thesekey characteristics: