Chapter4.tex

% LaTeX source for textbook ``How to think like a computer scientist''
% Copyright (C) 1999  Allen B. Downey
% Copyright (C) 2009  Thomas Scheffler


\chapter{Conditionals and recursion}
\label{condrecursion}


\section{Conditional execution}
\index{conditional}
\index{statement!conditional}

In order to write useful programs, we almost always need the ability
to check certain conditions and change the behavior of the program
accordingly.  {\bf Conditional statements} give us this ability.  The
simplest form is the {\tt if} statement:

\begin{verbatim}
  if (x > 0) 
  {
      printf ("x is positive\n");
  }
\end{verbatim}
%
The expression in parentheses is called the condition.
If it is true, then the statements in brackets get executed.
If the condition is not true, nothing happens.

\index{operator!comparison}
\index{comparison!operator}

The condition can contain any of the {\bf comparison operators}:

\begin{verbatim}
    x == y               /* x equals y */
    x != y               /* x is not equal to y */
    x > y                /* x is greater than y */
    x < y                /* x is less than y */
    x >= y               /* x is greater than or equal to y */
    x <= y               /* x is less than or equal to y */
\end{verbatim}
%
Although these operations are probably familiar to you, the
syntax C uses is a little different from mathematical
symbols like $=$, $\neq$ and $\le$.  A common error is
to use a single {\tt =} instead of a double {\tt ==}.  Remember
that {\tt =} is the assignment operator, and {\tt ==} is
a comparison operator.  Also, there is no such thing as
{\tt =<} or {\tt =>}.

The two sides of a condition operator have to be the same
type.  You can only compare {\tt ints} to {\tt ints} and
{\tt doubles} to {\tt doubles}.  Unfortunately, at this
point you can't compare strings at all!  There is
a way to compare strings, but we won't get to it for a couple
of chapters.

\section{The modulus operator}
\index{modulus}
\index{operator!modulus}

The modulus operator works on integers (and integer expressions)
and yields the {\em remainder} when the first operand is divided
by the second.  In C, the modulus operator is a percent sign,
{\tt \%}.  The syntax is exactly the same as for other operators:

\begin{verbatim}
  int quotient = 7 / 3;
  int remainder = 7 % 3;
\end{verbatim}
%
The first operator, integer division, yields 2.  The second
operator yields 1.  Thus, 7 divided by 3 is 2 with 1 left over.

The modulus operator turns out to be surprisingly useful.  For
example, you can check whether one number is divisible by
another: if {\tt x \% y} is zero, then {\tt x} is divisible
by {\tt y}.

Also, you can use the modulus operator to extract the rightmost
digit or digits from a number.  For example, {\tt x \% 10} yields
the rightmost digit of {\tt x} (in base 10).  Similarly
{\tt x \% 100} yields the last two digits.

\section {Alternative execution}
\label{alternative}
\index{conditional!alternative}

A second form of conditional execution is alternative execution,
in which there are two possibilities, and the condition determines
which one gets executed.  The syntax looks like:

\begin{verbatim}
  if (x%2 == 0)
  {
      printf ("x is even\n");
  } 
  else 
  {
      printf ("x is odd\n");
  }
\end{verbatim}
%
If the remainder when {\tt x} is divided by 2 is zero, then
we know that {\tt x} is even, and this code displays a message
to that effect.  If the condition is false, the second
set of statements is executed.  Since the condition must
be true or false, exactly one of the alternatives will be
executed.

As an aside, if you think you might want to check the parity
(evenness or oddness) of numbers often, you might want to
``wrap'' this code up in a function, as follows:

\begin{verbatim}
  void PrintParity (int x) 
  {
      if (x%2 == 0) 
      {
          printf ("x is even\n");
      } 
      else 
      {
          printf ("x is odd\n");
      }
  }
\end{verbatim}
%
Now you have a function named {\tt PrintParity()} that will display
an appropriate message for any integer you care to provide.
In {\tt main()} you would call this function as follows:

\begin{verbatim}
   PrintParity (17);
\end{verbatim}
%
Always remember that when you {\em call} a function, you do
not have to declare the types of the arguments you provide.
C can figure out what type they are.  You should resist the
temptation to write things like:

\begin{verbatim}
   int number = 17;
   PrintParity (int number);         /* WRONG!!! */
\end{verbatim}

\section {Chained conditionals}
\index{conditional!chained}

Sometimes you want to check for a number of related conditions
and choose one of several actions.  One way to do this is by
{\bf chaining} a series of {\tt if}s and {\tt else}s:

\begin{verbatim}
    if (x > 0) 
    {
        printf ("x is positive\n");
    } 
    else if (x < 0) 
    {
        printf ("x is negative\n");
    } 
    else 
    {
        printf ("x is zero\n");
    }
\end{verbatim}
%
These chains can be as long as you want, although they can
be difficult to read if they get out of hand.  One way to
make them easier to read is to use standard indentation,
as demonstrated in these examples.  If you keep all the
statements and squiggly-braces lined up, you are less
likely to make syntax errors and you can find them more
quickly if you do.

\section{Nested conditionals}
\index{conditional!nested}

In addition to chaining, you can also nest one conditional
within another.  We could have written the previous example
as:

\begin{verbatim}
    if (x == 0) 
    {
        printf ("x is zero\n");
    } 
    else 
    {
        if (x > 0) 
        {
            printf ("x is positive\n");
        }
        else 
        {
            printf ("x is negative\n");
        }
    }
\end{verbatim}
%
There is now an outer conditional that contains two branches.  The
first branch contains a simple output statement, but the second
branch contains another {\tt if} statement, which has two branches
of its own.  Fortunately, those two branches are both output
statements, although they could have been conditional statements as
well.

Notice again that indentation helps make the structure
apparent, but nevertheless, nested conditionals get difficult to read
very quickly.  In general, it is a good idea to avoid them when you
can.

\index{nested structure}

On the other hand, this kind of {\bf nested structure} is common, and
we will see it again, so you better get used to it.

\section{The {\tt return} statement}
\index{return}
\index{statement!return}

The {\tt return} statement allows you to terminate the execution
of a function before you reach the end.  One reason to use it
is if you detect an error condition:

\begin{verbatim}
  #include <math.h>

  void PrintLogarithm (double x) 
  {
      if (x <= 0.0) 
      {
          printf ("Positive numbers only, please.\n");
          return;
      }

     double result = log (x);
     printf ("The log of x is %f\n", result);
  }
\end{verbatim}
%
This defines a function named {\tt PrintLogarithm()} that takes
a {\tt double} named {\tt x} as a parameter.  The first thing
it does is check whether {\tt x} is less than or equal to
zero, in which case it displays an error message and then uses
{\tt return} to exit the function.  The flow of execution
immediately returns to the caller and the remaining lines of
the function are not executed.

I used a floating-point value on the right side of the condition
because there is a floating-point variable on the left.

Remember that any time you want to use one a function from the math
library, you have to include the header file {\tt math.h}.

\section{Recursion}
\label{recursion}
\index{recursion}

I mentioned in the last chapter that it is legal for one function to
call another, and we have seen several examples of that.  I neglected
to mention that it is also legal for a function to call itself.  It
may not be obvious why that is a good thing, but it turns out to be
one of the most magical and interesting things a program can do.

For example, look at the following function:

\begin{verbatim}
  void Countdown (int n) 
  {
      if (n == 0) 
      {
          printf ("Blastoff!");
      }
      else
      {
          printf ("%i", n);
          Countdown (n-1);
      }
  }
\end{verbatim}
%
The name of the function is {\tt Countdown()} 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()}---itself---passing
{\tt n-1} as an argument.

What happens if we call this function like this:

\begin{verbatim}
  int main (void)
  {
       Countdown (3);
       return EXIT_SUCCESS;
  }
\end{verbatim}
%
The execution of {\tt Countdown()} begins with {\tt n=3}, and
since {\tt n} is not zero, it outputs the value 3, and then
calls itself...

\begin{quote}
The execution of {\tt Countdown()} begins with {\tt n=2}, and
since {\tt n} is not zero, it outputs the value 2, and then
calls itself...

\begin{quote}
The execution of {\tt Countdown()} begins with {\tt n=1}, and
since {\tt n} is not zero, it outputs the value 1, and then
calls itself...

\begin{quote}
The execution of {\tt Countdown()} begins with {\tt n=0}, and
since {\tt n} is zero, it outputs the word ``Blastoff!''
and then returns.
\end{quote}

The Countdown that got {\tt n=1} returns.

\end{quote}

The Countdown that got {\tt n=2} returns.

\end{quote}

The Countdown that got {\tt n=3} returns.

\noindent And then you're back in {\tt main()} (what a trip).  So the
total output looks like:

\begin{verbatim}
    3
    2
    1
    Blastoff!
\end{verbatim}
%
As a second example, let's look again at the functions
{\tt PrintNewLine()} and {\tt PrintThreeLines()}.

\begin{verbatim}
  void PrintNewLine () 
    {
        printf ("\n");
    }

  void PrintThreeLines () 
    {
        PrintNewLine ();  PrintNewLine ();  PrintNewLine ();
    }
\end{verbatim}
%
Although these work, they would not be much help if I wanted
to output 2 newlines, or 106.  A better alternative would be

\begin{verbatim}
    void PrintLines (int n) 
    {
        if (n > 0) 
        {
            printf ("\n");
            PrintLines (n-1);
        }
    }
\end{verbatim}
%
This program is similar to {\tt Countdown}; as long as {\tt n} is
greater than zero, it outputs one newline, and then calls itself to
output {\tt n-1} additional newlines.  Thus, the total number of
newlines is {\tt 1 + (n-1)}, which usually comes out to roughly {\tt
n}.

\index{recursive}
\index{newline}

The process of a function calling itself is called {\bf recursion}, and
such functions are said to be {\bf recursive}.

\section {Infinite recursion}

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, {\em without making any recursive calls}.
This case---when the function completes without making a recursive
call---is called the {\bf base case}.

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
{\bf infinite recursion}, and it is generally not considered a good
idea.

\index{recursion!infinite}
\index{infinite recursion}
\index{run-time error}

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).

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

\section {Stack diagrams for recursive functions}
\index{stack}
\index{stack diagram}
\index{diagram!state}
\index{diagram!stack}

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.

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

This figure shows a stack diagram for Countdown, called
with {\tt n = 3}:

\vspace{0.1in}
\centerline{\epsfig{figure=figs/stack2.pdf,width=6cm}}
\vspace{0.1in}
%
There is one instance of {\tt main()} and four instances of
{\tt Countdown()}, each with a different value for the parameter
{\tt n}.  The bottom of the stack, {\tt Countdown()} with {\tt n=0}
is the base case.  It does not make a recursive call, so there
are no more instances of {\tt Countdown()}.

The instance of {\tt main()} is empty because {\tt main()} does not
have any parameters or local variables.  As an exercise, draw a
stack diagram for {\tt PrintLines()}, invoked with the parameter {\tt n=4}.


\section{Glossary}

\begin{description}

\item[modulus:]  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 \%}).

\item[conditional:]  A block of statements that may or may not
be executed depending on some condition.

\item[chaining:]  A way of joining several conditional statements
in sequence.

\item[nesting:] Putting a conditional statement inside one or both
branches of another conditional statement.

\item[recursion:]  The process of calling the same function you
are currently executing.

\item[infinite recursion:]  A function that calls itself
recursively without every reaching the base case.  Eventually
an infinite recursion will cause a run-time error.

\index{modulus}
\index{conditional}
\index{conditional!chained}
\index{conditional!nested}
\index{recursion}
\index{recursion!infinite}
\index{infinite recursion}

\end{description}


\section{Exercises}
\setcounter{exercisenum}{0}


\input{exercises/Exercise_4_english}