algorithm design and recursion there are one or more base cases for which no recursion is required all chains of recursion eventually end up at one of the base cases the simplest way to guarantee that these two conditions are met is to make sure that each recursion always occurs on smaller version of the original problem very small version of the problem that can be solved without recursion then becomes the base case this is exactly how the factorial definition works recursive functions you already know that the factorial can be computed using loop with an accumulator that implementation has natural correspondence to the original definition of factorial can we also implement version of factorial that follows the recursive definitionif we write factorial as separate functionthe recursive definition translates directly into code def fact( )if = return elsereturn fact( - do you see how the definition that refers to itself turns into function that calls itselfthis is called recursive function the function first checks to see if we are at the base case = andif soreturns if we are not yet at the base casethe function returns the result of multiplying by the factorial of - the latter is calculated by recursive call to fact( - think you will agree that this is reasonable translation of the recursive definition the really cool part is that it actually workswe can use this recursive function to compute factorial values from recfact import fact fact( fact( some beginning programmers are surprised by this resultbut it follows naturally from the semantics for functions that we discussed way back in remember that each call to function starts that function anew that means it has its own copy of any local valuesincluding the values of the parameters figure shows the sequence of recursive calls that computes note especially how each return value is multiplied by value of appropriate for each function invocation the values of are stored on the way down the chain and then used on the way back up as the function calls return there are many problems for which recursion can yield an elegant and efficient solution the next few sections present examples of recursive problem solving