recursion and induction let us prove (somewhatrigorously that the recursive number-printing program works to do sowe'll use proof by induction theorem the recursive number-printing algorithm is correct for > proof (by induction on the number of digits in nfirstif has one digitthen the program is trivially correctsince it merely makes call to printdigit assume then that printout works for all numbers of or fewer digits number of digits is expressed by its first digits followed by its least significant digit but the number formed by the first digits is exactly / whichby the inductive hypothesisis correctly printedand the last digit is mod so the program prints out any ( + )-digit number correctly thusby inductionall numbers are correctly printed this proof probably seems little strange in that it is virtually identical to the algorithm description it illustrates that in designing recursive programall smaller instances of the same problem (which are on the path to base casemay be assumed to work correctly the recursive program needs only to combine solutions to smaller problemswhich are "magicallyobtained by recursioninto solution for the current problem the mathematical justification for this is proof by induction this gives the third rule of recursion design rule assume that all the recursive calls work this rule is important because it means that when designing recursive programsyou generally don' need to know the details of the bookkeeping arrangementsand you don' have to try to trace through the myriad of recursive calls frequentlyit is extremely difficult to track down the actual sequence of recursive calls of coursein many cases this is an indication of good use of recursionsince the computer is being allowed to work out the complicated details the main problem with recursion is the hidden bookkeeping costs although these costs are almost always justifiablebecause recursive programs not only simplify the algorithm design but also tend to give cleaner coderecursion should not be used as substitute for simple for loop we'll discuss the overhead involved in recursion in more detail in section when writing recursive routinesit is crucial to keep in mind the four basic 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 design rule assume that all the recursive calls work compound interest rule never duplicate work by solving the same instance of problem in separate recursive calls