.. _recursion-recursion:

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.

.. index::
   single: recursion
   single: recursive function

.. note::
   The process of a function calling itself is called **recursion**, and
   such functions are said to be **recursive**.

For example, look at the following function:

::

    void countdown (int n) {
      if (n == 0) {
        cout << "Blastoff!\n";
      } else {
        cout << n << '\n';
        countdown (n - 1);
      }
    }

The name of the function is ``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
``countdown`` —itself— passing ``n - 1`` as an argument.

Watch how the countdown function works when we start with a value
of 3.

.. tb-code:: cpp
   :name: recursion_codelens_1
   :show-tutor:
   :caption: Recursion

   #include <iostream>
   using std::cout;

   void countdown (int n) {
       if (n == 0) {
           cout << "Blastoff!\n";
       } else {
           cout << n << '\n';
           countdown (n-1);
       }
   }

   int main () {
       countdown (3);
       return 0;
   }

What happens if we call ``countdown`` function like this:

  The execution of ``countdown`` begins with ``n = 3``, and since n is not zero, it
  outputs the value 3, and then calls itself...

      The execution of ``countdown`` begins with ``n = 2``, and since n is not zero,
      it outputs the value 2, and then calls itself...

          The execution of ``countdown`` begins with ``n = 1``, and since n is not
          zero, it outputs the value 1, and then calls itself...

              The execution of ``countdown`` begins with ``n = 0``, and since n is
              zero, it outputs the word “Blastoff!” and then returns.

          The ``countdown`` that got ``n = 1`` returns.

      The ``countdown`` that got ``n = 2`` returns.

  The ``countdown`` that got ``n = 3`` returns.

And then you’re back in ``main`` (what a trip). So the total output looks
like:

::

    3
    2
    1
    Blastoff!

As a second example, let’s look again at the functions ``new_line`` and
``three_line``.

::

    void new_line () {
      cout << '\n';
    }

    void three_line () {
      new_line ();  new_line ();  new_line ();
    }

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

::

    void repeat_lines (int n) {
      if (n > 0) {
        cout << '\n';
        repeat_lines (n - 1);
      }
    }

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

.. index:: random

You can have a little bit of fun with recursion.  Try this guessing game below!

.. tb-code:: cpp
   :name: recursion_AC_2
   :caption: Guessing Game.

   #include <iostream>
   #include <random>

   void guess_number(int num) {
       using std::cin;
       using std::cout;
       cout << "Enter your guess: ";
       int guess;
       cin >> guess;
       if (guess == num) {
           cout << "That's it!";
       }
       else if (guess > num) {
           cout << "Too high! ";
           guess_number(num);
       }
       else {
           cout << "Too low! ";
           guess_number(num);
       }
   }

   int main() {
       // make a random number generator
       std::random_device r;
       std::default_random_engine eng(r());

       int random_number = std::uniform_int_distribution<int> {1, 100} (eng);
       guess_number(random_number);
   }


.. tb-group::
   :name: self_check

   .. tb-tab:: Q1

      .. tb-choice::
         :name: recursion_1

         What will print?

         ::

             #include <iostream>
             using namespace std;

             void exclamation_point(int n) {
               if (n > 0) {
                 cout << '!';
                 exclamation_point (n-1);
               }
             }

             int main () {
               exclamation_point(3);
             }


         - [ ] !

           The function keeps executing while n is greater than 0.
         - [ ] !!

           The function keeps executing while n is greater than 0.
         - [x] !!!

           Correct! First, the program enters the if statement within exclamation_point because n is greater than 0. Then the function prints a "!" and calls itself again, but with n-1, which is 2. This repeats until n is 0, which is when the program exits the function.
         - [ ] !!!!

           The function keeps executing while n is greater than 0. Therefore, when n is 0, it will not print a "!"

   .. tb-tab:: Q2

      .. tb-choice::
         :name: recursion_2

         What will print?

         ::

             #include <iostream>
             using namespace std;

             void exclamation_point(int n) {
               if (n > 0) {
                 cout << '!';
                 exclamation_point (n-1);
               }
             }

             int main () {
               exclamation_point(0);
             }


         - [ ] !!

           If we start at zero, will the function ever call itself?
         - [ ] !

           If we start at zero, will the function ever call itself?
         - [ ] 0

           The only output statement in this program prints a "!", therefore "0" would never print.
         - [x] Nothing prints.

           Correct! The program never enters the "if" statement within the function because n is never greater than 0.

   .. tb-tab:: Q3

      .. tb-blank::
         :name: recursion_3

         A function that calls itself is said to be {{blank}}.

         .. tb-answer::
            :match: recursive
            :feedback: And the process by which a function calls itself is called recursion.
            :incorrect: Try again!