there are several important and possibly confusing points about recursion common question isisn' this just circular logicthe answer is that although we are defining function in terms of itselfwe are not defining particular instance of the function in terms of itself in other wordsevaluating ( by computing ( would be circular evaluating ( by computing ( is not circular--unlessof coursef( is evaluated by eventually computing ( the two most important issues are probably the how and why questions in the how and why issues are formally resolved we will give an incomplete description here it turns out that recursive calls are handled no differently from any others if is called with the value of then line requires the computation of ( thusa call is made to compute ( this requires the computation of ( thereforeanother call is made to compute ( this means that ( must be evaluated to do sof( is computed as * ( )+ * nowf( must be evaluated since this is base casewe know priori that ( this enables the completion of the calculation for ( )which is now seen to be then ( ) ( )and finally ( can be determined all the bookkeeping needed to keep track of pending function calls (those started but waiting for recursive call to complete)along with their variablesis done by the computer automatically an important pointhoweveris that recursive calls will keep on being made until base case is reached for instancean attempt to evaluate (- will result in calls to (- ) (- )and so on since this will never get to base casethe program won' be able to compute the answer (which is undefined anywayoccasionallya much more subtle error is madewhich is exhibited in figure the error in figure is that bad( is definedby line to be bad( obviouslythis doesn' give any clue as to what bad( actually is the computer will thus repeatedly make calls to bad( in an attempt to resolve its values eventuallyits bookkeeping system will run out of spaceand the program will terminate abnormally generallywe would say that this function doesn' work for one special case but is correct otherwise this isn' true heresince bad( calls bad( thusbad( cannot be evaluated either furthermorebad( )bad( )and bad( all make calls to bad( since bad( is not evaluablenone of these values are either in factthis program doesn' work for any nonnegative value of nexcept with recursive programsthere is no such thing as "special case these considerations lead to the first two fundamental rules of recursion base cases you must always have some base caseswhich can be solved without recursion making progress for the cases that are to be solved recursivelythe recursive call must always be to case that makes progress toward base case int badint ifn = return else return badn figure nonterminating recursive function