suppose you are going to write recursive function to calculate the factorial of number fact(nreturns where the factorial of zero is defined to be what would be the most appropriate base case = = > < converting an integer to string in any base suppose you want to convert an integer to string in some base between binary and hexadecimal for exampleconvert the integer to its string representation in decimal as " ,or to its string representation in binary as " while there are many algorithms to solve this problemincluding the algorithm discussed in the stack sectionthe recursive formulation of the problem is very elegant let' look at concrete example using base and the number suppose we have sequence of characters corresponding to the first digitslike conv_string " it is easy to convert number less than to its string equivalent by looking it up in the sequence for exampleif the number is then the string is conv_string[ or " if we can arrange to break up the number into three single-digit numbers and then converting it to string is simple number less than sounds like good base case knowing what our base is suggests that the overall algorithm will involve three components reduce the original number to series of single-digit numbers convert the single digit-number to string using lookup concatenate the single-digit strings together to form the final result the next step is to figure out how to change state and make progress toward the base case since we are working with an integerlet' consider what mathematical operations might reduce number the most likely candidates are division and subtraction while subtraction might workit is unclear what we should subtract from what integer division with remainders gives us clear direction let' look at what happens if we divide number by the base we are trying to convert to using integer division to divide by we get with remainder of this gives us two good results firstthe remainder is number less than our base that can be converted to string immediately by lookup secondwe get number that is smaller than our original and moves us toward the base case of having single number less than our base now our job is to convert to its string representation again we will use integer division plus remainder to get results of and respectively finallywe have reduced the problem to converting which we can do easily since it satisfies the base case condition of <basewhere base the series of operations we have just performed is illustrated in figure notice that the numbers we want to remember are in the remainder boxes along the right side of the diagram what is recursion