Schedule‎ > ‎

Lesson 14 Animation and Recursion


13.3: Computer Animation

Objectives

At the end of the lesson the student will be able to:

  • Explain the principles of animation
  • Create code for simple animation
  • Write code for animation objects


13.3.1: Introduction to Computer Animation


  • Animation is the illusion of motion created by displaying a series of images or shapes
  • For example, the following animation displays at 10 frames per second (FPS):
    • The speed of the display is fast enough that you cannot easily see the individual frames
    • Contrast this with the following image that displays at 2 frames per second:
      bouncing ball 2
    • At 2 FPS, the animation is slow enough that you can see the individual frames
    • Both of these animations were produced by displaying these images, known as frames:
      animation example 3
    • The speed with which the frames are displayed is known as the framerate
    • Note that these images are in the public domain and were obtained from Wikipedia

    Animation Loop

    • To create movement over time, we use an animation loop
    • There are three steps to an animation loop as shown in the following diagram:
    • During the update portion of the loop, the computer calculates the position of each shape
    • During the render portion, the computer draws our shapes
    • Then the computer waits (pauses) a short while before repeating the process
    • There are two reasons for waiting:
      1. To slow down the animation's frame rate
      2. To allow other programs on the computer to run
    • The second reason is important but not always obvious
    • A modern operating system runs several programs at the same time
    • At some point, other programs need a chance to run
    • A good time for other programs to run is when our program does not need to run

    Check Yourself

    1. Animation is the ________ of motion created by displaying a series of images or shapes.
    2. True or false: if the animation is too fast, it appears jerky.
    3. Each image in an animation is sometimes called a ________.
    4. True or false: one reason for pausing during an animation is to allow other programs on the computer time to run.


    13.3.2: Animating Shapes

    • Here is the SFML project we used in the last section: start-sfml
      • Download this zip file to c:\CodeBlocks\Projects
      • This project assumes the same setup as the instructions and school PCs
      • If your setup is different, you will need to start a new SFML project
    • Recall that an animation loop has three steps:
      1. Update
      2. Render
      3. Sleep
    • During the update phase of the loop our code calculates the position of our objects
    • For example, if we had an sf::CircleShape named circ we would code:
      circ.move(dx, dy);
      
    • During the render phase we:
      1. Start with a call to the window clear() function
        win.clear()
      2. Then we call the draw() function of each object
        win.draw(circ);
      3. We end the render phase with a call to the window display() function
        win.display()
    • When running an animation, we may get visual artifacts such as screen tearing
    • Screen tearing is a visual anomaly where a display device shows information from two or more video frames in a single screen draw
    • To reduce these visual artifacts, we set the vertical synchronization to match our monitor
      win.setVerticalSyncEnabled(true);
      
    • After this function call, our application runs at the same frequency as the monitor's refresh rate
    • SFML then automatically pauses after each display
    • Most LCD monitors run at 60 frames per second
    • For more information see: Controlling the framerate

    Example Animation

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    
    #include <SFML/Graphics.hpp>
    
    int main()
    {
        sf::RenderWindow win(sf::VideoMode(600, 400), "Anim1");
        win.setVerticalSyncEnabled(true);
    
        // Setup
        const float RADIUS = 30.f;
        sf::CircleShape circ(RADIUS);
        circ.setFillColor(sf::Color::Green);
        float dx = 2.5f;
        float dy = 0.0f;
    
        // Animation loop
        while (win.isOpen())
        {
            // Event polling to control window closing
            sf::Event event;
            while (win.pollEvent(event))
            {
                if (event.type == sf::Event::Closed)
                {
                    win.close();
                }
            }
            // Update
            circ.move(dx, dy);
            // Render
            win.clear();
            win.draw(circ);
            win.display(); // start sleep part of cycle
        }
    
        return 0;
    }
    

    More Information


    13.3.3: Bouncing off the Walls

    • To make our animation more interesting, we can add a bounce to the circle
    • Imagine the circle is a ball and that we want the ball to bounce off the walls
    • Imitating a real thing or process is known as a simulation
    • One use of computers is simulating, or modeling, key characteristic of systems
    • For our simulation, we use the sides, top and bottom of the window as the walls
    • Remember that our coordinate system starts in the window at (0, 0)
    • The x-coordinate is always positive and increases to the right
    • The y-coordinate is always positive and increases in the downward direction
      Window coordinates

    Finding the Walls

    • We know that when x == 0 our shape is at the left side of the window
    • Similarly, when y == 0 our shape is at the top of the window
    • We can find the size of the window by calling the window getSize() function
      sf::Vector2u size = win.getSize();
      
    • The width == size.x and the height == size.y
    • We can find the position of our ball by calling the getPosition() function
      sf::Vector2f pos = circ.getPosition();
      
    • The left side of the ball is at pos.x and the top is at pos.y
    • To test if the ball exceeds the boundaries in the x-direction, we use an if-else statement like:
      if (pos.x < 0)
      {
          dx = SPEED_X;
      }
      else if (pos.x + RADIUS * 2 > size.x)
      {
          dx = -SPEED_X;
      }
      
    • If the ball exceeds the boundaries we reverse its direction
    • Similarly, we test if the ball exceeds the top and bottom boundaries with:
      if (pos.y < 0)
      {
          dy = SPEED_Y;
      }
      else if (pos.y + RADIUS * 2 > size.y)
      {
          dy = -SPEED_Y;
      }
      
    • The bounce code goes in the update portion of the animation loop as shown in the following example

    Example Animation With Bounce

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    
    #include <cmath>
    #include <SFML/Graphics.hpp>
    
    int main()
    {
        sf::RenderWindow win(sf::VideoMode(600, 400), "Anim2");
        win.setVerticalSyncEnabled(true);
        const float RADIUS = 30.f;
        const float SPEED_X = 2.5f;
        const float SPEED_Y = 2.5f;
        sf::CircleShape circ(RADIUS);
        circ.setFillColor(sf::Color::Green);
        float dx = SPEED_X;
        float dy = SPEED_Y;
    
        while (win.isOpen())
        {
            sf::Event event;
            while (win.pollEvent(event))
            {
                if (event.type == sf::Event::Closed)
                {
                    win.close();
                }
            }
            // Update
            sf::Vector2u size = win.getSize();
            sf::Vector2f pos = circ.getPosition();
            if (pos.x < 0)
            {
                dx = std::abs(dx);
            }
            else if (pos.x + RADIUS * 2 > size.x)
            {
                dx = -std::abs(dx);
            }
            if (pos.y < 0)
            {
                dy = std::abs(dy);
            }
            else if (pos.y + RADIUS * 2 > size.y)
            {
                dy = -std::abs(dy);
            }
            circ.move(dx, dy);
            // Render
            win.clear();
            win.draw(circ);
            win.display();
        }
    
        return 0;
    }
    


    13.3.4: Animating Two Objects

    • If we want to animate two shapes, we need separate variables for each object
    • As we add more shape objects, our code in the animation loop becomes more cluttered
    • To avoid the clutter and duplication, we can encapsulate the code for the shape in a class
    • Here is a Ball class that encapsulates the information for the moving shape
    • We add a new file to Code::Blocks with File > New > Empty File
    • Following the Ball class is an animation application bouncing two balls
    • Notice how simple the animation loop remains

    Ball Class Header File (ball.h)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    #include <SFML/Graphics.hpp>
    #ifndef BALL_H
    #define BALL_H
    
    const float RADIUS = 30.f;
    
    class Ball
    {
    public:
        Ball();
        Ball(float x, float y, float speed, sf::Color ballColor);
        void update(sf::RenderWindow& win);
        void draw(sf::RenderWindow& win);
    private:
        sf::CircleShape circ;
        float dx, dy;
    };
    #endif
    

    Ball Class Implementation File (ball.cpp)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    
    #include <cmath>
    #include "ball.h"
    
    Ball::Ball()
    {
        const float SPEED = 2.5f;
        circ = sf::CircleShape(RADIUS);
        circ.setFillColor(sf::Color::Green);
        dx = SPEED;
        dy = SPEED;
    }
    
    Ball::Ball(float x, float y, float speed, sf::Color ballColor)
    {
        circ = sf::CircleShape(RADIUS);
        circ.setFillColor(ballColor);
        circ.setPosition(x, y);
        dx = speed;
        dy = speed;
    }
    
    void Ball::update(sf::RenderWindow& win)
    {
        sf::Vector2u winSize = win.getSize();
        sf::Vector2f pos = circ.getPosition();
        if (pos.x < 0)
        {
            dx = std::abs(dx);
        }
        else if (pos.x + RADIUS * 2 > winSize.x)
        {
            dx = -std::abs(dx);
        }
        if (pos.y < 0)
        {
            dy = std::abs(dy);
        }
        else if (pos.y + RADIUS * 2 > winSize.y)
        {
            dy = -std::abs(dy);
        }
        circ.move(dx, dy);
    }
    
    void Ball::draw(sf::RenderWindow& win)
    {
        win.draw(circ);
    }
    

    Example Animation With Two Balls (main.cpp)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    
    #include <SFML/Graphics.hpp>
    #include "ball.h"
    
    int main()
    {
        sf::RenderWindow win(sf::VideoMode(600, 400), "Anim3");
        win.setVerticalSyncEnabled(true);
    
        // Random speed
        srand(time(0));
        float speed = 2.0f + ((float) rand() / RAND_MAX);
        Ball b1 = Ball(1, 1, speed, sf::Color::Red);
        speed = 2.0f + ((float) rand() / RAND_MAX);
        Ball b2 = Ball(100, 1, speed, sf::Color::Green);
    
        while (win.isOpen())
        {
            sf::Event event;
            while (win.pollEvent(event))
            {
                if (event.type == sf::Event::Closed)
                {
                    win.close();
                }
            }
            // Update
            b1.update(win);
            b2.update(win);
            // Render
            win.clear();
            b1.draw(win);
            b2.draw(win);
            win.display();
        }
    
        return 0;
    }
    


    13.3.6: Animating Many Objects

    • We can take our animation one step further and animate many objects
    • To juggle several balls at once we use a list such as a vector or array with a counting loop
    • We can see the loops with the vector in the following example

    Example Animation With Many Balls

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    
    #include <vector>
    #include <SFML/Graphics.hpp>
    #include "ball.h"
    
    int main()
    {
        srand(time(0));
        sf::RenderWindow win(sf::VideoMode(600, 400), "Anim4");
        win.setVerticalSyncEnabled(true);
    
        const int NUM_BALLS = 10;
        std::vector<Ball> balls(NUM_BALLS);
        const int NUM_COLORS = 6;
        const sf::Color colors[] =
        {
            sf::Color::Red, sf::Color::Green, sf::Color::Blue,
            sf::Color::Yellow, sf::Color::Magenta, sf::Color::Cyan
        };
    
        // Initialize vector of balls
        for (unsigned i = 0; i < balls.size(); i++)
        {
            float x = rand() % 550;
            float y = rand() % 350;
            float speed = 2.0f + ((float) rand() / RAND_MAX);
            balls[i] = Ball(x, y, speed, colors[i % NUM_COLORS]);
        }
    
        while (win.isOpen())
        {
            sf::Event event;
            while (win.pollEvent(event))
            {
                if (event.type == sf::Event::Closed)
                {
                    win.close();
                }
            }
            // Update
            for (unsigned i = 0; i < balls.size(); i++)
            {
                balls[i].update(win);
            }
            // Render
            win.clear();
            for (unsigned i = 0; i < balls.size(); i++)
            {
                balls[i].draw(win);
            }
            win.display();
        }
    
        return 0;
    }
    


    Exercise 13.3: Simple Animation (5m)

    In this exercise we compile and run the example application showing the animation of several shapes.

    Specifications

    1. Start an SFML project in Code::Blocks by:
      1. Right-clicking start-sfml, selecting "Save Link As...", and saving the link to a convenient location like the Desktop.
      2. Unzip the file and open the folder named start-sfml.
      3. Double-click the start-sfml.cbp to open Code::Blocks.

      For more information see lesson 13.2.2: Starting a Graphical Project. If your setup is different than the school computers, you will need to start a new SFML project.

    2. Add a new file named ball.h to the project with File > New > Empty Fileand copy the following code into the file:
      #include <SFML/Graphics.hpp>
      #ifndef BALL_H
      #define BALL_H
      
      const float RADIUS = 30.f;
      
      class Ball
      {
      public:
          Ball();
          Ball(float x, float y, float speed, sf::Color ballColor);
          void update(sf::RenderWindow& win);
          void draw(sf::RenderWindow& win);
      private:
          sf::CircleShape circ;
          float dx, dy;
      };
      #endif
      
    3. Add a new file named ball.cpp to the project with File > New > Empty File and copy the following code into the file:
      #include <cmath>
      #include "ball.h"
      
      Ball::Ball()
      {
          const float SPEED = 2.5f;
          circ = sf::CircleShape(RADIUS);
          circ.setFillColor(sf::Color::Green);
          dx = SPEED;
          dy = SPEED;
      }
      
      Ball::Ball(float x, float y, float speed, sf::Color ballColor)
      {
          circ = sf::CircleShape(RADIUS);
          circ.setFillColor(ballColor);
          circ.setPosition(x, y);
          dx = speed;
          dy = speed;
      }
      
      void Ball::update(sf::RenderWindow& win)
      {
          sf::Vector2u winSize = win.getSize();
          sf::Vector2f pos = circ.getPosition();
          if (pos.x < 0)
          {
              dx = std::abs(dx);
          }
          else if (pos.x + RADIUS * 2 > winSize.x)
          {
              dx = -std::abs(dx);
          }
          if (pos.y < 0)
          {
              dy = std::abs(dy);
          }
          else if (pos.y + RADIUS * 2 > winSize.y)
          {
              dy = -std::abs(dy);
          }
          circ.move(dx, dy);
      }
      
      void Ball::draw(sf::RenderWindow& win)
      {
          win.draw(circ);
      }
      
    4. Copy the following code into the main.cpp file:
      #include <vector>
      #include <SFML/Graphics.hpp>
      #include "ball.h"
      
      int main()
      {
          srand(time(0));
          sf::RenderWindow win(sf::VideoMode(600, 400), "Anim4");
          win.setVerticalSyncEnabled(true);
      
          const int NUM_BALLS = 10;
          std::vector<Ball> balls(NUM_BALLS);
          const int NUM_COLORS = 6;
          const sf::Color colors[] =
          {
              sf::Color::Red, sf::Color::Green, sf::Color::Blue,
              sf::Color::Yellow, sf::Color::Magenta, sf::Color::Cyan
          };
      
          // Initialize vector of balls
          for (unsigned i = 0; i < balls.size(); i++)
          {
              float x = rand() % 550;
              float y = rand() % 350;
              float speed = 2.0f + ((float) rand() / RAND_MAX);
              balls[i] = Ball(x, y, speed, colors[i % NUM_COLORS]);
          }
      
          while (win.isOpen())
          {
              sf::Event event;
              while (win.pollEvent(event))
              {
                  if (event.type == sf::Event::Closed)
                  {
                      win.close();
                  }
              }
              // Update
              for (unsigned i = 0; i < balls.size(); i++)
              {
                  balls[i].update(win);
              }
              // Render
              win.clear();
              for (unsigned i = 0; i < balls.size(); i++)
              {
                  balls[i].draw(win);
              }
              win.display();
          }
      
          return 0;
      }
      
    5. Build and run your project to verify the animation works correctly.

      If you have problems ask a classmate or the instructor for help.

    6. Take a few minutes to experiment with the number of objects in the animation.
    7. Turn this main.cpp into Canvas.

    14.1: Running Under Windows - skipped

    Learner Outcomes

    At the end of the lesson the student will be able to:

    • Run console programs under Windows


    14.1.1: About DLL's

    • We can run our compiled programs under Windows, on computers without Cygwin installed
    • To accomplish this, we need to include the appropriate Cygwin DLL's
    • DLL stands for Dynamic Link Library
    • A DLL is a binary file that provides a library of functions for use by Windows applications
    • All programs running under Windows use DLL's
    • Any DLL that a program uses must be available on the computer where the application is running

    Cygwin DLL's

    • Cygwin provides a number of DLL's
    • These DLL's are located in the cygwin/bin directory
    • They are easy to identify because they have an extension of .dll
    • Your programs uses one or more of these DLL's when they run
    • Any DLL that your program uses must be accessible to the program
    • Thus, to run your program on a computer without Cygwin installed, we need to include a copy of the needed Cygwin DLL's


    14.1.2: Finding the DLL's We Need

    • The easiest way to find the DLL's your program needs is to run the program under Windows
    • Whenever the program needs a DLL, it attempts to load the DLL
    • When it cannot load the DLL, it fails and identifies the DLL it needs
      need for dll
    • To fix the problem, we copy the needed DLL into the same directory as your application
    • Since the computers in our classroom have paths set to the Cygwin\bin directory, we need to delete the path setting for this test:
      path=.

    Example of Finding Needed DLL's

    • We want to run the playagain.cpp program under Windows
    • We save the program to the desktop and compile it using TextPad
    • Next we launch a Windows console:
      1. From the Start menu, Select Run...
      2. In the text box type cmd and press the Enter key
    • Then we remove the path to cygwin\bin by typing:
      path=.
    • Now when we try to run the program, we get an error message
    • We locate the Cygwin DLL we need in the cygwin\bin directory and copy it to the desktop
    • Now we can successfully run the application

    Example Application

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    #include <iostream>
    using namespace std;
    
    int main() {
        char repeat = 'y';
        while ('y' == repeat) {
            cout << "\nPlaying an exciting game!\n";
            cout << "Do you want to play again? (y/n) ";
            cin >> repeat;
        }
        cout << "\nThanks for playing!\n";
    
        return 0;
    }
    


    Exercise 14.1: Running on Windows without Cygwin (5m)

    In this exercise we run a program under Windows without starting Cygwin or using TextPad.

    Specifications

    1. Choose an application, compile it and copy the .exe file to the desktop
    2. Open a Window's terminal window:
      1. Click the Start button
      2. Select "Run..."
      3. In the Open box type in: cmd
      4. Press the Enter key
    3. Change to the Desktop directory:
      cd Desktop
      
    4. Set the path on the computer to '.':
      path=.
    5. Run the .exe file and find the missing DLL's

      To run in the Windows terminal, type the program name (no ./ needed).

    6. Copy the missing DLL's to the Desktop and run again


    14.1.3: Summary

    • We can run C++ programs compiled in Cygwin on Windows computers without Cygwin installed
    • To make your programs work, we need to include any required DLL's
      • This is true for any Windows application
    • The easiest way to find the needed DLL is to run your program in the Windows terminal
    • When your program needs a DLL, Windows will try to load it
    • When Windows cannot load the DLL, it gives an error message identifying the missing DLL
    • To fix the problem, we copy the DLL into the directory in which we put your .exe file

    Check Yourself

    1. What is a DLL?
    2. Why do your programs need DLL's?
    3. How can you add the DLL's needed to make your program run?


    14.2: Reviewing Functions - skipped


    14.3: Introduction to Recursion

    Learner Outcomes

    At the end of the lesson the student will be able to:

    • Design recursive algorithms
    • Code recursive functions
    • Trace the processing steps of recursive functions


    recursion man
    The Most Interesting Man in the
    World's Secret Power: Recursion

    14.3.1: About Recursion

    Recursion: when an algorithm is defined by referring to itself until a specified condition is met.

    • Recursion is a natural approach to some problems
    • It allows us to break down a problem into one or more subproblems similar in form to the original problem
      • Sounds circular, but in practice is not
    • Recursion divides the problem into two parts:
      • Recursive step
      • Base case
    • The recursive step solves part of the problem and then calls the same function
    • Since the recursive step solves part of the problem, it passes a smaller problem to the recursive function
    • Eventually the smaller problem becomes easy enough to just solve
    • The easy-to-solve problem is known as the base case

    Recursion Example: Many Hands Make Light Work

    • What if you were asked to do some repetitive task like washing the dishes?
    • You look at the pile of dishes and realize we have better things to do
    • So you wash one dish and then ask someone else to wash the dishes
      • Then you leave as soon as possible
    • The next person notices your actions and decides to do the same
    • They wash one dish and then ask someone else to wash the dishes
    • This sequence repeats until all the dishes are washed and the sink is empty
    • Writing this as an algorithm, we have:

    Algorithm For Washing Dishes

    • If the sink is empty, do nothing
    • Else:
      • Wash one dish
      • Ask someone else to wash the dishes

    Recursive Elements

    • Notice the recursive nature of the algorithm
    • The "else" clause calls itself:
      • To do the dishes, we ask someone else to do the dishes
    • To make sure this algorithm is not an endless passing of the buck, each person does some work
    • This makes the job passed to the next person smaller
    • When all the dishes are done, the chain of asking someone else to do the dishes is broken

    Check Yourself

    1. True or false: a recursive step needs to solve some part of a problem.
    2. The easy-to-solve part of a recursion is know as the ________ case.
    3. True or false: every recursive algorithm must have a base case.


    14.3.2: Implementing Recursive Functions

    • Now that we see how recursion works, let us look at how to implement it in a program
    • We implement recursion in C++ using functions
    • Each function contains a conditional statement
    • One of the statements contains a call the same function
    • This structure is shown below:
      returnType recursiveFunction(parameters) {
          if (stopping condition) { // base case
              // Problem is very easy
              // so solve it and return
          }
          // recursive step
          // Solve part of the problem
          // leaving a smaller problem
          recursiveFunction(arguments);
          // after the recursive step
          return xxx; // depending on return type
      }
      
    • Like a loop, a recursive function must have some way to end
    • We often write the base case first and the recursive step second
    • The code below implements our recursive example

    Implementation of Recursive Example

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    
    #include <iostream>
    using namespace std;
    
    void wash(int count);
    
    int main() {
        int count;
        cout << "How many dishes to wash? ";
        cin >> count;
        wash(count);
    }
    
    void wash(int count) {
        if (count == 0) { // stopping condition
            cout << "Done washing dishes\n";
            return;
        }  else {
           cout << count << " dishes to wash." << endl;
           wash(count - 1); // recursive step
           cout << "Washed " << count << " dishes so far." << endl;
           return; // optional for void functions
        }
    
    }

    14.3.2a  Try It: Writing a Recursive Function (5m)

    1. Copy the following program into a text editor, save it as recursion.cpp, and then compile and run the starter program to make sure you copied it correctly.
      #include <iostream>
      using namespace std;
      
      int main() {
          // Enter your code here
      
          return 0;
      }
      
    2. Add a stub for a void function named recursiveCounter that has a single int parameter named counter
    3. Within main() add the following code to call the recursiveCounter() function:
      int counter;
      cout << "What number to count from? ";
      cin >>  counter;
      recursiveCounter(num);
      
    4. In the recursiveCounter() function, add code to print the numbers from num to 0 recursively. Do NOT use a loop statement.

      Hint: Look at the code for the washing dishes example.

    5. Save your code for the next Try-It.
    6. Check to see if the student on either side of you needs help. If so, offer to help them.
    7. Be prepared to answer the following questions.

    Check Yourself

    1. True or false: Recursion is a form of looping but without using a loop statement.
    2. Recursion is implemented in C++ using function calls and ________.
    3. In recursive algorithms, an if-statement is needed to test for the ________ case.
    4. What are the elements of using recursion to loop?


    14.3.3: How Recursion Works

    • To understand how recursion works, we must consider a data structure known as a stack
    • A stack is like a pile of dishes:
      stack of dishes
    • When a dish is placed on the stack, it is placed on top
    • Similarly, when a dish is removed from the stack, it is taken from the top
    • The last dish put on the stack is the first dish removed from the stack:
      • Otherwise you get a lot of broken dishes

    Function Call Stack

    • Whenever we call a function, the computer sets aside a block of memory for that function
    • The memory is used to store the local variables and return address
    • The return address is the point in the code immediately after where the function was called
    • This memory is allocated in an area of the computer known as the call stack
    • The information saved is known as the stack frame or activation record
    • Every function call creates a new stack frame
    • Every time a function returns, the stack frame data is popped off the stack

    Call Stack for wash(3)
    call stack diagram

    Video: Data Structures Using C++: Illustration of Recursive Function Calls (Call Stack)

    Check Yourself

    1. Items are placed on the top of a stack and removed from the ________.
    2. True or false: the last item placed on a stack is the first item removed.
    3. Functions are tracked on a call stack with a stack ________.
    4. True or false: a function on a call stack is active and has yet to complete execution.


    14.3.4: Pre- and Post-Recursion

    • Remember the structure of the recursive case in our dish washing example
      cout << count << " dishes to wash." << endl;
      wash(count - 1); // recursive step
      cout << "Washed " << count << " dishes so far.\n";
      
    • Before the recursive call are statements showing the number of dishes to wash
      cout << count << " dishes to wash." << endl;
      
    • Then comes the recursive call:
      wash(count - 1); // includes prerecursion: count - 1
      
    • After the recursive call another statement is executed:
      cout << "Washed " << count << " dishes so far." << endl;
      
    • Within the recursive case, code executed before the recursive call is known as pre-recursion
    • Code executed after the recursive call is known as post recursion
    • Notice that the calculation (count - 1) is made before the recursion (pre-recursion)

    Some Recursion Terminology
    recursion terminology

    14.3.4a  Try It: Exploring Pre- and Post-Recursion (3m)

    1. Start with your code from the last Try It: Writing a Recursive Function.
    2. After the recursive call, add a print statement to display the value of num like:
      cout << "After the recursive call counter is " << counter << endl;
      
    3. Compile and run your code to see the output of this post recursion statement.
    4. Save your code as an example for the next Exercise.
    5. When finished, please help those around you.
    6. Be prepared to answer the following Check Yourself questions when called upon.

    Check Yourself

    1. True or false: within the recursive step, code executed before the recursive call is known as pre-recursion.
    2. Within the recursive step, code executed after the recursive call is known as ________ recursion.
    3. In the following recursive code, the pre-recursion calculation is ________.
      void rec(int num) {
          if (num <= 0) {
              cout << num << endl;
              return;
          }
          cout << num << endl;
          rec(num - 1);
          cout << num << endl;
      }
      
    4. In the above recursive code, the post-recursion statement is ________.
    5. What is the effect of pre-recursion vs. post-recursion?


    14.3.5: Developing a Recursive Algorithm

    • Before we write recursive functions, we must develop a recursive algorithm
    • To develop a recursive algorithm, we must find a way to do the following:
      1. Use a solution to a smaller or easier version of a problem to arrive at the solution itself
      2. Know when the problem is small enough to solve directly
    • As another example of recursion, let us look at exponentiation
    • We will limit ourselves to positive integers
    • The mathematical notation for exponentiation is:

      xy

    • A function prototype for exponentiation could be:
      int power(int x, int y);
      
    • The definition of exponentiation when y is a positive integer is:

      xy = 1 * x * x * x ... (y times)

    • As we can see, the operation corresponds to repeated multiplication
    • Another way to express the operation is as a recurrence relation

      xy = x * xy - 1

    • The recurrence relation shows the recursive step we need for our algorithm

    Thinking Recursively

    • We start developing the algorithm by working through the process by hand
    • It seems like a lot of work, and so we consider how to get someone else to do most of the work
    • If we could get someone else to calculate xy - 1, we could just multiply by x one time
    • This process could repeat until we are done
    • How would we know when we were done?

    Recursive Algorithm For Exponentiation

    • If y is 0, we are done and the result is x0, which is 1
    • Else (while y ≥ 1):
      • Ask someone else to compute xy - 1
      • We multiply the result of xy - 1 times x

    Activity: Calculating 2x

    1. For this activity we will calculate 2x using the power of student brains.
    2. You will be asked for the answer to 2x, where x is an integer value.
    3. If the value of x is one or less then say the answer.

      For example, say: "21 is 2."

    4. Otherwise, ask the student next to you for the value of 2x - 1

      For example, if you were asked for 214 , ask the student next to you: "What is 213?"

    5. When you get an answer to your question, double it and say the answer out loud.

      For example, if you get an answer to 213, say: "214 is 16,384."

    Check Yourself

    1. True or false: exponentiation with positive integers corresponds to repeated multiplication.
    2. The following is known as a ________ relation.

      xy = x * xy - 1

    3. The base case of our recursive algorithm occurs when y is equal to ________.


    Exercise 14.3  Recursive Exponention   power.cpp

    1.  Start with the following code.  Save it as power.cpp
    #include <iostream>
    using namespace std;
    
    int power(int x, int y);
    
    int main() {
        int x = 0, y = 0;
        cout << "Enter the base: ";
        cin >> x;
        cout << "Enter the exponent: ";
        cin >> y;
        cout << x << "^" << y << " = " << power(x, y) << endl;
        return 0;
    }
    
    int power(int x, int y) {
         //add your code here
         return 0;
    }
    



    2.  Fill in the power function.
    3.  Remember that in this case each call of the recursive function returns a calculated value
    4.  Look at your notes on the factorial (recursive) function for an example.
    5.  Submit it as power.cpp to Canvas Exercise 14.3


    14.3.6 Tracing the Structure

    • Which line of code in the above is the recursive call? 
    • Which line(s) of code is the base case? 

    Tracing the Execution

    • To see how a recursive function works, we can add print statement to trace the flow
    • As an example, we trace power(2, 3) called from main():
      main() calls power(2, 3)
        power(2, 3) calls power(2, 2)
          power(2, 2) calls power(2, 1)
            power(2, 1) calls power(2, 0)
              power(2, 0) returns 1 (base case)
            power(2, 1) returns 2
          power(2, 2) returns 4
        power(2, 3) returns 8
      power(2, 3) returns 8 to main()
      
    • Note that the first half of the trace makes successive function calls
      • Until the base case is reached
    • The second half returns the values from the recursive calls

    Instrumented Source Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    
    #include <iostream>
    using namespace std;
    
    int power(int x, int y);
    
    int main() {
        int x = 0, y = 0;
        cout << "Enter the base: ";
        cin >> x;
        cout << "Enter the exponent: ";
        cin >> y;
        cout << "main() calls power(" << x << ", " << y << ")\n";
        cout << "power(" << x << ", " << y << ") returns "
             << power(x, y) << " to main()\n";
        return 0;
    }
    
    int power(int x, int y) {
        if (y == 0) {
            cout << "power(" << x
                 << ", 0) returns 1 (base case)\n";
            return 1;
        }
        cout << "power(" << x << ", " << y << ") "
             << "calls power(" << x << ", "
             << (y - 1) << ")\n";
        y = y - 1; // pre-recursion
        int result = power(x, y); // recursion
        result = result * x; // post-recursion
        cout << "power(" << x << ", " << (y + 1)
             << ") returns " << result << endl;
        return result;
    }
    

    Check Yourself

    1. When a recursive function calls itself, that step known as the ________ step.
    2. True or false: the base case always includes a recursive function call.
    3. True or false: the recursive step must always define a task that is easier, smaller or closer to completion than the original task.
    4. In the following recursive code, the pre-recursion calculation is ________.
      int power(int x, int y) {
          if (y == 0) {
              return 1;
          } else {
              int result = power(x, y - 1);
              return x * result;
          }
      }
      
    5. In the above recursive code, the post-recursion calculation is ________.


    14.3.7: Using Recursion with Input Validation

    • Recall our discussion of input validation in lesson 6.1.7
    • We can put this input validation code inside a function as shown below:

    Example of Input Validation Function with Loop

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    
    #include <iostream>
    using namespace std;
    
    // Function to read a double
    double readNumber(string prompt) {
        double input = 0.0;
        bool isError = true;
        do {
            cout << prompt;
            cin >> input;
            if (cin.fail()) {
                cout << "Please enter numbers only!\n";
                cin.clear();
                cin.ignore(1000, '\n');
            } else {
                isError = false;
            }
        } while (isError);
        return input;
    }
    
    // Main function for testing.
    int main() {
        double num = readNumber("Enter a number: ");
        cout << "You entered: " << num << endl;
    
        return 0;
    }
    
    • To allow a user to reenter data we coded a loop, else clause and a control variable isError
      double readNumber(string prompt) {
          double input = 0.0;
          bool isError = true;
          do {
              cout << "Enter a number: ";
              double input = 0.0;
              cin >> input;
              if (cin.fail()) {
                  cout << "Please enter numbers only!\n";
                  cin.clear();
                  cin.ignore(1000, '\n');
              } else {
                  isError = false;
              }
          } while (isError);
          return input;
      }
      
    • The loop, else-clause and control variable complicate the code
    • We can simplify the code by using recursion instead:
      double readNumber() {
          double input = 0.0;
          cout << "Enter a number: ";
          cin >> input;
          if (cin.fail()) {
              cout << "Please enter numbers only!\n";
              cin.clear();
              cin.ignore(1000, '\n');
              return readNumber();
          }
          return input;
      }
      
    • Notice how much shorter and simpler the code looks
    • The do-while loop and else clause are replaced by a function call
    • All we needed to repeat the input operation when an error occurs was one line:
      return readNumber();

    Example of Input Validation with Recursion

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    
    #include <iostream>
    using namespace std;
    
    // Recursive function to read a double
    double readNumber(string prompt) {
        double input = 0.0;
        cout << prompt;
        cin >> input;
        if (cin.fail()) {
            cout << "Please enter numbers only!\n";
            cin.clear();
            cin.ignore(1000, '\n');
            return readNumber(prompt);
        }
        return input;
    }
    
    // Main function for testing.
    int main() {
        double num = readNumber("Enter a number: ");
        cout << "You entered: " << num << endl;
    
        return 0;
    }
    


    Pair Programming


    Learner Outcomes

    • At the end of the lesson the student will be able to:
    • Describe how to complete an assignment using pair programming
    • Discuss the pros and cons of pair programming

    Introduction to Pair Programming

    • Pair programming is a style of programming in which two people work together on one computer at the same time:
      • Exactly two people: not one nor three or more
      • Exactly one computer: not two or more
    • One person enters the code and the other reviews each line of code as it is entered

    Roles

    • The person operating the mouse and keyboard is called the driver
    • The other person in the pair is called the navigator
    • The role of the navigator is to think about what needs to be done and where the project is going
    • The navigator duties may include:
      • Determining optimal algorithms
      • Analyzing the design and code to prevent errors
    • Each person "drives" about half the time:
      • Physically get up and move positions when switching roles to emphasize the change

    Working Together

    • More than 75% of your time must be spent working on the projects together
    • The objective is to work together and to learn from each other
    • You cannot divide the work into two pieces with each partner working on a separate piece
    • If you are not both engaged in the process, you will not learn the material
    • People who do not learn the material fail the course

    Why Pair Program?

    • Students who pair program report:
      • Higher confidence in a program solution
      • More satisfaction with programming
    • Instructors report higher completion and passing rates

    Videos Explaining Pair Programming:

    https://www.youtube.com/watch?v=5ySLQ5_cQ34

    Fun with Pair Programming: a professionally developed video (10 minutes)

    Fun with Pair Programming Worksheet: follow along during the video

    Check Yourself

    1. True or false: pair programming typically results in fewer errors and programs take less time to complete.
    2. The job of the driver is to ________.
    3. The job of the navigator is to ________.
    4. To gain a different perspective on the problem being solved, after about 30 minutes change ________.
    5. True or false: in pair-programming, the person who owns the code is the person who wrote the code.

    More Information


    Best Practices
    • You may choose any other student in this class for a partner or you will be assigned a partner
      • You may NOT program with a person from outside the class
      • Often in the workplace, you will not have your choice of partner
    • Both of your names appear on the assignment
    • When choosing partners and working together, certain practices help you perform better
    • Pair-programmers are usually more successful when they have similar experience levels
    • However, pair programming can work with partners of different experience levels
      • The more experienced partner must be ready to mentor rather than just develop the program
    • Find a partner with whom you can easily exchange ideas
    • If you cannot work easily with someone, get another partner or work by yourself

    The Rules of Pair Programming

    Refer to the rules to verify you are pair programming correctly!

    Pair Programming Non-Performance (source)

    • Silence immediately indicates a lack of collaboration
    • Disengagement when one member does not pay attention or does something else like email or texting
    • One member observes and offers little comment as they "watch the master"

    Check Yourself

    1. True or false: there are no rules in pair programming.
    2. Indicators of poor pair programming performance include ________.
      1. one member is not paying attention
      2. one member observes and offers little comment as they "watch the master"
      3. silence
      4. all of these
    3. True or false: the rules of pair-programming require you to use only one computer at a time to edit and compile code.

    More Information


    Exercise 14.4: Recursion Functions

    In this exercise we look at several examples of recursion. Use this starter code to get started:

    recfun-starter.cpp

    Save the solutions in a file named recfun.cpp and turn the file in with your project. Uncomment the recursive function calls in main() as you progress. 

    Recursive Problems

    1. Write a function named printDown() using recursion to print numbers from n to 0.

      Example output:

      Enter a positive number: 3
      Counting down: 3 2 1 0
      

      See Try It: Writing a Recursive Function for more information. Call the function from main().

    2. Write a function named printUp() using recursion to print numbers from 0 to n.

      Example output:

      Counting up: 0 1 2 3
      

      Hint: Remember the discussion of pre- and post recursion. You only need to move the output statement of the previous problem to solve this one. See Try It: Exploring Pre- and Post-Recursion for more information.

    3. Write a function using recursion named printStars() that receives a single int parameter and returns nothing. It the parameter value is greater than zero, the function prints to the console the given number of asterisks; otherwise it does nothing. For instance, calling printStars(8) displays: ******** (8 asterisks).
    4. Example output:

      Printing stars: ***
      
    5. We have a number of bunnies and each bunny has two big floppy ears. Write a non-member function named bunnyEars() that computes the total number of ears for zero or more bunnies recursively without loops, multiplication or division.

      Example results of calling the bunnyEars() function:

      bunnyEars(0) -> 0
      bunnyEars(1) -> 2
      bunnyEars(2) -> 4
      bunnyEars(3) -> 6
      
      Example output:
      Counting bunny ears: bunnyEars(3) -> 6
      

      Hint: If you know the number of ears on bunnyEars(n - 1), how many more ears are there on bunnyEars(n)? The bunnyEars() function needs to return the number of bunny ears.

    6. Write a recursive function named factorial() that computes a factorial for n, denoted mathematically by n!, where n! is the product of all positive integers less than or equal to n.

      Examples of factorials:

      factorial(0) = 1 (by definition)
      factorial(1) = 1
      factorial(2) = 2 * 1 = 2
      factorial(3) = 3 * 2 * 1 = 6
      factorial(4) = 4 * 3 * 2 * 1 = 24
      
      Example output:
      Factorial of 3: 6
      

      Hint: The function needs to return a number.

    7. Write a recursive function named sum() that totals the values between 1 and n, where n is any positive integer.

      Examples of summing:

      sum(1) = 1
      sum(2) = 2 + 1 = 3
      sum(3) = 3 + 2 + 1 = 6
      sum(4) = 4 + 3 + 2 + 1 = 10
      
      Example output:
      Summing numbers 1 to 3: 6
      

      Hint: The function needs to return a number.

    8. We want to write a function named digits() which finds the number of digits needed to represent an integer. For example, digits(1234) is 4 because 1234 has four digits (1, 2, 3, and 4). Here is a trace of the function calls:
      digits(1234)
      = digits(123) + 1
      = digits(12) + 1 + 1
      = digits(1) + 1 + 1 + 1
      = 1 + 1 + 1 + 1
      

      Compute the algorithm without loops using recursion. Call digits() with the following code in the main() function:

      // Other function calls here
      cout << "\nCounting the number of digits in an integer";
      int testValue;
      
      cout << "Please enter a number: ";
      cin >>  testValue;
      
      int numDigits = digits(testValue);
      cout << "You need " << numDigits << " digits to represent "
           << testValue << " in decimal\n";
      
      Example output:
      Please enter another number: 12345
      You need 5 digits to represent 12345 in decimal
      

      Hint: repeatedly call n / 10 until reaching n < 10.

    9. Write a function using recursion that displays a string in reverse with signature void printReversed(string myString, int index);  Do not use arrays, loops or additional strings. Example output:
      Enter a string: abcdef
      String reversed: fedcba
      

      Recall from lesson 3.2.6 that you can access part of a string using the substr() function. Also, you can determine the length of a string using the length() function. Also, you can use square bracket notation to access a single character as discussed in lesson 6.2.2.  Hint:  In each recursive call,  you will pass it a substring of the original string without the first character.  After the recursive call you will print out that first character.  

    10. Turn your recfun.cpp to Canvas Ex. 14.4



    14.3.8: Summary

    • Recursion is when an algorithm is defined in terms of itself
    • It allows us to define subproblems similar in form to the original
    • Recursion always has two parts:
      • Base case
      • A problem that is closer to the solution
    • Eventually, the base case is always called
    • Without the base case, we would have infinite recursion
    • Code executed before the cursive call is known as pre-recursion
    • Code executed after the call is known as post recursion
    • Recursion makes some code shorter and easier to understand, such as input validation

    Recursion Humor

    More Information on Recursion


    Subpages (1): recfun.cpp
    Comments