TheThreeLawsofRecursion.ptx

<section xml:id="recursion_the-three-laws-of-recursion">
        <title>The Three Laws of Recursion</title>
        <p>Like the robots of Asimov, all recursive algorithms must obey three
            important laws:</p>
        <blockquote>
            <p><ol marker="1">
                <li>
                    <p>A recursive algorithm must have a <term>base case</term>.</p>
                </li>
                <li>
                    <p>A recursive algorithm must change its state and move toward the base
                        case.</p>
                </li>
                <li>
                    <p>A recursive algorithm must call itself, recursively.</p>
                </li>
            </ol></p>
        </blockquote>
        <p>Let's look at each one of these laws in more detail and see how it was
            used in the <c>vectsum</c> algorithm. First, a <term>base case</term> is the condition
            that allows the algorithm to stop recursing.<idx>base case</idx> A base case is typically a
            problem that is small enough to solve directly. In the <c>vectsum</c>
            algorithm the base case is a list of length 1.</p>
        <p>To obey the second law, we must arrange for a change of state that moves
            the algorithm toward the base case. A change of state means that some
            data that the algorithm is using is modified. Usually the data that
            represents our problem gets smaller in some way. In the <c>vectsum</c>
            algorithm our primary data structure is a vector, so we must focus our
            state-changing efforts on the vector. Since the base case is a list of
            length 1, a natural progression toward the base case is to shorten the
            vector. This is exactly what happens on line 5 of <xref ref="lst-recsum-cpp"/> when we call <c>vectsum</c> with a shorter list.</p>
        <p>The final law is that the algorithm must call itself. This is the very
            definition of recursion. Recursion is a confusing concept to many
            beginning programmers. As a novice programmer, you have learned that
            functions are good because you can take a large problem and break it up
            into smaller problems. The smaller problems can be solved by writing a
            function to solve each problem. When we talk about recursion it may seem
            that we are talking ourselves in circles. We have a problem to solve
            with a function, but that function solves the problem by calling itself!
            But the logic is not circular at all; the logic of recursion is an
            elegant expression of solving a problem by breaking it down into smaller
            and easier problems.</p>
        <p>It is important to note that regardless of whether or not a recursive function
            implements these three rules, it may still take an unrealistic amount of time
            to compute (and thus not be particularly useful). A great example of this is the
            ackermann function (shown in <xref ref="ackermann"/>), named after Wilhelm Ackermann, which recursively expands to
            unrealistic proportions. An example as to how many calls this function makes to
            itself is the case of ackermann(4,3). In this case, it calls itself well over 100
            billion times, with an average time of expected completion that falls after the
            predicted end of the universe. Despite this, it will eventually come to an answer,
            but you probably won't be around to see it. This goes to show that the efficiency
            of recursive functions are largely dependent on how they're implemented.</p>

    <listing xml:id="ackermann">
        <caption>Ackermann Function</caption>
        <program interactive="activecode" language="cpp" label="ackermann-prog"><input>
//ackermann function example
#include &lt;iostream&gt;
using namespace std;

unsigned int ackermann(unsigned int m, unsigned int n) {
   if (m == 0) {//Base case
      return n + 1;
   }
   if (n == 0) {
      return ackermann(m - 1, 1);// subtract, move to base case
   }
   //notice a call to the ackermann function as a parameter
   //for another call to the ackermann function. This is where
   //it gets unrealistically complicated.
   return ackermann(m - 1, ackermann(m, n - 1));//subtract here too
}

int main(){
   //compute the ackermann function.
   //Try replacing the 1,2 parameters with 4,3 and see what happens
   cout &lt;&lt; ackermann(1,2) &lt;&lt; endl;
   return 0;
}
        </input></program>
    </listing>
        <p>In the remainder of this chapter we will look at more examples of
            recursion. In each case we will focus on designing a solution to a
            problem by using the three laws of recursion.</p>
<reading-questions xml:id="rq-three-laws-recursion">
    <exercise label="question_recsimp_1">
        <statement>

            <p>Why is a base case needed in a recursive function?</p>

        </statement>
<choices>

            <choice>
                <statement>
                    <p>If a recursive function didn't have a base case, then the function would end too early.</p>
                </statement>
                <feedback>
                    <p>Incorrect. The complete opposite would happen instead.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>If a recursive function didn't have a base case, then the function would return an undesired outcome.</p>
                </statement>
                <feedback>
                    <p>Incorrect. In fact, the program wouldn't return anything.</p>
                </feedback>
            </choice>

            <choice correct="yes">
                <statement>
                    <p>If a recursive function didn't have a base case, then the function would continue to make recursive calls creating an infinite loop.</p>
                </statement>
                <feedback>
                    <p>Correct! a base case is needed to end the continuous recursive calls, so that the program doesn't get stuck in a never ending loop.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>If a recursive function didn't have a base case, then the function would not be able to ever make recursive calls in the first place.</p>
                </statement>
                <feedback>
                    <p>Incorrect. Recursive calls will continue to be called even without a base case.</p>
                </feedback>
            </choice>
</choices>

    </exercise>

    <exercise label="question_recsimp_2">
        <statement>

            <p>How many recursive calls are made when computing the sum of the vector {2,4,6,8,10}?</p>

        </statement>
<choices>

            <choice>
                <statement>
                    <p>6</p>
                </statement>
                <feedback>
                    <p>There are only five numbers on the vector, the number of recursive calls will not be greater than the size of the vector.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>5</p>
                </statement>
                <feedback>
                    <p>The initial call to vectsum is not a recursive call.</p>
                </feedback>
            </choice>

            <choice correct="yes">
                <statement>
                    <p>4</p>
                </statement>
                <feedback>
                    <p>the first recursive call passes the vector {4,6,8,10}, the second {6,8,10} and so on until [10].</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>3</p>
                </statement>
                <feedback>
                    <p>This would not be enough calls to cover all the numbers on the vector</p>
                </feedback>
            </choice>
</choices>

    </exercise>

    <exercise label="question_recsimp_3">
        <statement>

            <p>Suppose you are going to write a recursive function to calculate the factorial of a number.  fact(n) returns n * n-1 * n-2 * <ellipsis/> Where the factorial of zero is defined to be 1.  What would be the most appropriate base case?</p>

        </statement>
<choices>

            <choice>
                <statement>
                    <p>n == 0</p>
                </statement>
                <feedback>
                    <p>Although this would work there are better and slightly more efficient choices. since fact(1) and fact(0) are the same.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>n == 1</p>
                </statement>
                <feedback>
                    <p>A good choice, but what happens if you call fact(0)?</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>n &gt;= 0</p>
                </statement>
                <feedback>
                    <p>This base case would be true for all numbers greater than zero so fact of any positive number would be 1.</p>
                </feedback>
            </choice>

            <choice correct="yes">
                <statement>
                    <p>n &lt;= 1</p>
                </statement>
                <feedback>
                    <p>Good, this is the most efficient, and even keeps your program from crashing if you try to compute the factorial of a negative number.</p>
                </feedback>
            </choice>
</choices>

    </exercise>
</reading-questions>   
<conclusion><p>
    <!-- extra space before the progress bar -->            
</p></conclusion>
    </section>