chapter04.html

think like a computer scientist

why that is a good thing, but it turns out to be one of the most magical and 
interesting things a program can do.</P>

<P>For example, look at the following function:</P>

<PRE>
void countdown (int n) {
  if (n == 0) {
    cout << "Blastoff!" << endl;
  } else {
    cout << n << endl;
    countdown (n-1);
  }
}
</PRE>

<P>The name of the function is <TT>countdown</TT> and it takes a single integer
as a parameter.  If the parameter is zero, it outputs the word ``Blastoff.''  
Otherwise, it outputs the parameter and then calls a function named 
<TT>countdown</TT>---itself---passing <TT>n-1</TT> as an argument.</P>

<P>What happens if we call this function like this:</P>

<PRE>
void main ()
{
  countdown (3);
}
</PRE>

<P>The execution of <TT>countdown</TT> begins with <TT>n=3</TT>, and since 
<TT>n</TT> is not zero, it outputs the value 3, and then calls itself...</P>

  <BLOCKQUOTE>
  The execution of <TT>countdown</TT> begins with <TT>n=2</TT>, and since 
  <TT>n</TT> is not zero, it outputs the value 2, and then calls itself...

    <BLOCKQUOTE>
    The execution of <TT>countdown</TT> begins with <TT>n=1</TT>, and since 
    <TT>n</TT> is not zero, it outputs the value 1, and then calls itself...

      <BLOCKQUOTE>
      The execution of <TT>countdown</TT> begins with <TT>n=0</TT>, and since 
      <TT>n</TT> is zero, it outputs the word ``Blastoff!'' and then returns.
      </BLOCKQUOTE>

    The countdown that got <TT>n=1</TT> returns.
    </BLOCKQUOTE>

  The countdown that got <TT>n=2</TT> returns.
  </BLOCKQUOTE>

<P>The countdown that got <TT>n=3</TT> returns.</P>

<P>And then you're back in <TT>main</TT> (what a trip).  So the total output 
looks like:</P>

<PRE>
3
2
1
Blastoff!
</PRE>

<P>As a second example, let's look again at the functions <TT>newLine</TT> and 
<TT>threeLine</TT>.</P>

<PRE>
void newLine () {
  cout << endl;
}

void threeLine () {
  newLine ();  newLine ();  newLine ();
}
</PRE>

<P>Although these work, they would not be much help if I wanted to output 2 
newlines, or 106.  A better alternative would be</P>

<PRE>
void nLines (int n) {
  if (n > 0) {
    cout << endl;
    nLines (n-1);
  }
}
</PRE>

<P>This program is similar to <TT>countdown</TT>; as long as <TT>n</TT> is 
greater than zero, it outputs one newline, and then calls itself to output 
<TT>n-1</TT> additional newlines.  Thus, the total number of newlines is 
<TT>1 + (n-1)</TT>, which usually comes out to roughly <TT>n</TT>.</P>


<P>The process of a function calling itself is called <B>recursion</B>, and
such functions are said to be <B>recursive</B>.</P>


<BR><BR>
<H3>4.8 Infinite recursion</H3>

<P>In the examples in the previous section, notice that each time the functions
get called recursively, the argument gets smaller by one, so eventually it gets
to zero.  When the argument is zero, the function returns immediately, 
<I>without making any recursive calls</I>. This case---when the function 
completes without making a recursive call---is called the <B>base case</B>.</P>

<P>If a recursion never reaches a base case, it will go on making recursive 
calls forever and the program will never terminate.  This is known as 
<B>infinite recursion</B>, and it is generally not considered a good idea.</P>

<P>In most programming environments, a program with an infinite recursion will 
not really run forever.  Eventually, something will break and the program will 
report an error.  This is the first example we have seen of a run-time error 
(an error that does not appear until you run the program).</P>

<P>You should write a small program that recurses forever and run it to see 
what happens.</P>


<BR><BR>
<H3>4.9 Stack diagrams for recursive functions</H3>

<P>In the previous chapter we used a stack diagram to represent the state of a 
program during a function call.  The same kind of diagram can make it easier to
interpret a recursive function.</P>

<P>Remember that every time a function gets called it creates a new instance 
that contains the function's local variables and parameters.</P>

<P>This figure shows a stack diagram for countdown, called with <TT>n = 3</TT>:
</P>

<P CLASS=1><IMG SRC="images/stack2.png" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/stack2.png" ALT="Stack2 Image"></P>

<P>There is one instance of <TT>main</TT> and four instances of 
<TT>countdown</TT>, each with a different value for the parameter <TT>n</TT>.
The bottom of the stack, <TT>countdown</TT> with <TT>n=0</TT> is the base case.
It does not make a recursive call, so there are no more instances of 
<TT>countdown</TT>.</P>

<P>The instance of <TT>main</TT> is empty because <TT>main</TT> does not have 
any parameters or local variables.  As an exercise, draw a stack diagram for 
<TT>nLines</TT>, invoked with the parameter <TT>n=4</TT>.</P>


<BR><BR>
<H3>4.10 Glossary</H3>

<DL>
  <DT>modulus:</DT><DD> An operator that works on integers and yields the 
  remainder when one number is divided by another.  In C++ it is denoted with 
  a percent sign (<TT>%</TT>).</DD>

  <DT>conditional:</DT><DD> A block of statements that may or may not be 
  executed depending on some condition.</DD>

  <DT>chaining:</DT><DD> A way of joining several conditional statements in 
  sequence.</DD>

  <DT>nesting:</DT><DD> Putting a conditional statement inside one or both
  branches of another conditional statement.</DD>

  <DT>recursion:</DT><DD>The process of calling the same function you are 
  currently executing.</DD>

  <DT>infinite recursion:</DT><DD>A function that calls itself recursively 
  without every reaching the base case.  Eventually an infinite recursion will 
  cause a run-time error.</DD>
</DL>

<BR>
<DIV CLASS=navigation><HR>
  <TABLE ALIGN=center WIDTH="100%" CELLPADDING=0 CELLSPACING=2>
  <TR>
    <TD><A HREF="chapter05.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter05.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="next" 
      SRC="images/next.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/next.gif"></A>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="up" 
      SRC="images/up.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/up.gif"></A>
    </TD>

    <TD><A HREF="chapter03.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter03.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="previous"
      SRC="images/previous.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/previous.gif"></A>
    </TD>

    <TD ALIGN=center BGCOLOR="#99CCFF" WIDTH="100%">
      <B CLASS=title>How to Think Like a Computer Scientist: Chapter 4</B>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="contents"
      SRC="images/contents.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/contents.gif"></A>
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>
  </TR>
  </TABLE>

  <B CLASS=navlabel>Next:</B>
  <SPAN CLASS=sectref><A HREF="chapter05.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter05.html">Chapter 5</A></SPAN>

  <B CLASS=navlabel>Up:</B>
  <SPAN CLASS=sectref><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">Index</A></SPAN>

  <B CLASS=navlabel>Previous:</B>
  <SPAN CLASS=sectref><A HREF="chapter03.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter03.html">Chapter 3</A></SPAN>

  <HR>
</DIV>
</BODY>
</HTML>