pythondsConvertinganIntegertoaStringinAnyBase.ptx

<section xml:id="recursion_converting-an-integer-to-a-string-in-any-base">
        <title>Converting an Integer to a String in Any Base</title>
        <p>Suppose you want to convert an integer to a string in some base between
            binary and hexadecimal. For example, convert the integer 10 to its
            string representation in decimal as <c>"10"</c>, or to its string
            representation in binary as <c>"1010"</c>. While there are many algorithms
            to solve this problem, including the algorithm discussed in the stack
            section, the recursive formulation of the problem is very
            elegant.</p>
        <p>Let's look at a concrete example using base 10 and the number 769.
            Suppose we have a sequence of characters corresponding to the first 10
            digits, like <c>convString = "0123456789"</c>. It is easy to convert a
            number less than 10 to its string equivalent by looking it up in the
            sequence. For example, if the number is 9, then the string is
            <c>convString[9]</c> or <c>"9"</c>. If we can arrange to break up the number
            769 into three single-digit numbers, 7, 6, and 9, then converting it to
            a string is simple. A number less than 10 sounds like a good base case.</p>
        <p>Knowing what our base is suggests that the overall algorithm will
            involve three components:</p>
        <blockquote>
            <p><ol marker="1">
                <li>
                    <p>Reduce the original number to a series of single-digit numbers.</p>
                </li>
                <li>
                    <p>Convert the single digit-number to a string using a lookup.</p>
                </li>
                <li>
                    <p>Concatenate the single-digit strings together to form the final result.</p>
                </li>
            </ol></p>
        </blockquote>
        <p>The next step is to figure out how to change state and make progress
            toward the base case. Since we are working with an integer, let's
            consider what mathematical operations might reduce a number. The most
            likely candidates are division and subtraction. While subtraction might
            work, it is unclear what we should subtract from what. Integer division
            with remainders gives us a clear direction. Let's look at what happens
            if we divide a number by the base we are trying to convert to.</p>
        <p>Using integer division to divide 769 by 10, we get 76 with a remainder
            of 9. This gives us two good results. First, the remainder is a number
            less than our base that can be converted to a string immediately by
            lookup. Second, we get a number that is smaller than our original and
            moves us toward the base case of having a single number less than our
            base. Now our job is to convert 76 to its string representation. Again
            we will use integer division plus remainder to get results of 7 and 6
            respectively. Finally, we have reduced the problem to converting 7,
            which we can do easily since it satisfies the base case condition of
            <m>n &lt; base</m>, where <m>base = 10</m>. The series of operations
            we have just performed is illustrated in <xref ref="fig-tostr"/>. Notice that
            the numbers we want to remember are in the remainder boxes along the
            right side of the diagram.</p>
        
        <figure align="center" xml:id="fig-tostr">
            <caption>Converting an Integer to a String in Base 10.</caption>
                <image source="Recursion/toStr.png" width="50%">
                <description><p>Flowchart demonstrating the conversion of an integer to a string in base 10 using recursion. The process starts with 'toStr(769)', which divides '769' by '10' and adds the remainder 'g'. The result feeds into 'toStr(76)', which again divides by '10' to add the remainder '6'. The final call is 'toStr(7)', which is less than '10' and therefore converts directly to '7'. The remainders at each step are used to build the string representation of the integer.</p></description>
                </image>
            </figure>

        <p><xref ref="expl-rectostr"/> shows the C++ and Python code that implements the algorithm
            outlined above for any base between 2 and 16.</p>
        <exploration xml:id="expl-rectostr">
            <title>Convert Integer to String</title>
            <task xml:id="lst-rectostr-cpp" label="lst-rectostr-cpp">
                <title>C++ Implementation</title>
                <statement><program xml:id="lst_rectostrcpp" interactive="activecode" language="cpp" label="lst_rectostrcpp-prog"><input>
//Recursive example of converting from int to string.

#include &lt;iostream&gt;
#include &lt;string&gt;
using namespace std;

string toStr(int n, int base) {
    string convertString = "0123456789ABCDEF";
    if (n &lt; base) {
        return string(1, convertString[n]); // converts char to string, and returns it
    } else {
        return toStr(n/base, base) + convertString[n%base]; // function makes a recursive call to itself.
    }
}

int main() {
  cout &lt;&lt; toStr(1453, 16);
}
                </input></program></statement>
            </task>
            <task xml:id="lst-rectostr-py" label="lst-rectostr-py">
                <title>Python Implementation</title>
                <statement><program xml:id="lst_rectostrpy" interactive="activecode" language="python" label="lst_rectostrpy-prog"><input>
#Recursive example of converting an int to str.

def toStr(n,base):
   convertString = "0123456789ABCDEF"
   if n &lt; base:
      return convertString[n]
   else:
      return toStr(n//base,base) + convertString[n%base] #function makes a recursive call to itself.

def main():
   print(toStr(1453,16))

main()
                </input></program></statement>
            </task>
        </exploration>
        <p>Notice that in line 7 we check for the base case where <c>n</c>
            is less than the base we are converting to. When we detect the base
            case, we stop recursing and simply return the string from the
            <c>convertString</c> sequence. In line 10 we satisfy both the
            second and third laws<ndash/>by making the recursive call and by reducing the
            problem size<ndash/>using division.</p>
        <p>Let's trace the algorithm again; this time we will convert the number 10
            to its base 2 string representation (<c>"1010"</c>).</p>
    
        <figure align="center" xml:id="fig-tostr2">
            <caption>Converting the Number 10 to its Base 2 String Representation.</caption>
                <image source="Recursion/toStrBase2.png" width="50%">
                <description><p>Flowchart depicting the recursive process of converting the number 10 to its binary (base 2) string representation. The topmost operation 'toStr(10)' shows the division '10 / 2' with a remainder '0'. This leads to 'toStr(5)', with division '5 / 2' and remainder '1', followed by 'toStr(2)' with division '2 / 2' and remainder '0', and finally 'toStr(1)' indicating '1 &lt; 2' and yielding a remainder '1'. The remainders collected at each step form the binary representation of the number 10.</p></description>
                </image>
            </figure>

        <p><xref ref="fig-tostr2"/> shows that we get the results we are looking for,
            but it looks like the digits are in the wrong order. The algorithm works
            correctly because we make the recursive call first on line
            6, then we add the string representation of the remainder.
            If we reversed returning the <c>convertString</c> lookup and returning the
            <c>toStr</c> call, the resulting string would be backward! But by delaying
            the concatenation operation until after the recursive call has returned,
            we get the result in the proper order. This should remind you of our
            discussion of stacks back in the previous chapter.</p>
 <reading-questions xml:id="rq-converting-integer-to-string">

    <exercise label="RecursiveQ1">
        <statement>

            <p>Is the process of stepping through a recursive function similar to the construct of a stack or a queue?</p>

        </statement>
<choices>

            <choice correct="yes">
                <statement>
                    <p>A stack, because a recursive function will complete the final function call before any of the other function calls, similar to how a stack has the Last-in-First-out principle.</p>
                </statement>
                <feedback>
                    <p>Correct! a recursive function will complete the final function call first, because the rest of the calls are waiting for the results of the calls they made.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>A queue, because a recursive function will complete its intial function call before any of the other function calls, similar to how a queue has the First-in-First-out principle.</p>
                </statement>
                <feedback>
                    <p>Incorrect. Think of it this way, when a function is called and it calls itself, the original function call cannot be completed until the new function call is completed.</p>
                </feedback>
            </choice>
</choices>

    </exercise>
            <p>Write a function that takes a string as a parameter and returns a new string that is the reverse of the old string. Hint: using the substr(strIndex1, strIndex2) method for returning specific sections of a string can help.</p>
            <blockquote>

    <program xml:id="recursion_sc_1cpp" interactive="activecode" language="cpp" label="recursion_sc_1cpp-prog">
        <input>
#include &lt;iostream&gt;
#include &lt;string&gt;
using namespace std;

void testEqual(string a, string b){
    if (a == b){
        cout &lt;&lt; "PASS" &lt;&lt; endl;
    }
    else{
        cout &lt;&lt; "Failed" &lt;&lt; endl;
    }
}

string reverse(string s){
    //Code Here
    return s;
}

int main(){
    testEqual(reverse("hello"),"olleh");
    testEqual(reverse("l"),"l");
    testEqual(reverse("follow"),"wollof");
    testEqual(reverse(""),"");

    return 0;
}
        </input>
    </program>
            </blockquote>
            <p>Write a function that takes a string as a parameter and returns True if the string is a palindrome, False otherwise.  Remember that a string is a palindrome if it is spelled the same both forward and backward.  For example:  radar is a palindrome.  for bonus points palindromes can also be phrases, but you need to remove the spaces and punctuation before checking.  for example:  madam i'm adam  is a palindrome.  Other fun palindromes include:</p>
            <p><ul>
                <li>
                    <p>kayak.</p>
                </li>
                <li>
                    <p>aibohphobia.</p>
                </li>
                <li>
                    <p>Live not on evil.</p>
                </li>
                <li>
                    <p>Reviled did I live, said I, as evil I did deliver.</p>
                </li>
                <li>
                    <p>Go hang a salami; I'm a lasagna hog.</p>
                </li>
                <li>
                    <p>Able was I ere I saw Elba.</p>
                </li>
                <li>
                    <p>Kanakanak <ndash/>  a town in Alaska.</p>
                </li>
                <li>
                    <p>Wassamassaw <ndash/> a town in South Dakota.</p>
                </li>
            </ul></p>
            <blockquote>

    <program xml:id="recursion_sc_2cpp" interactive="activecode" language="cpp" label="recursion_sc_2cpp-prog">
        <input>
#include &lt;iostream&gt;
#include &lt;string&gt;
using namespace std;

void testEqual(bool a, bool b){
    if (a == b){
        cout &lt;&lt; "PASS" &lt;&lt; endl;
    }
    else{
        cout &lt;&lt; "Failed" &lt;&lt; endl;
    }
}

string removeWhite(string s) {
    //Code Here
    return s;
}

bool isPal(string s) {
    //Code Here
    return false;
}

int main(){
    testEqual(isPal(removeWhite("x")),true);
    testEqual(isPal(removeWhite("radar")),true);
    testEqual(isPal(removeWhite("hello")),false);
    testEqual(isPal(removeWhite("")),true);
    testEqual(isPal(removeWhite("hannah")),true);
    testEqual(isPal(removeWhite("madam i'm adam")),true);

    return 0;
}
        </input>
    </program>
            </blockquote>
        </reading-questions>  
        <conclusion><p>
            <!-- extra space before the progress bar -->            
        </p></conclusion> 
    </section>