Basic Solutions: Recursion and Iteration

Quick Links

• Problem Statement and Resources
• Lab 1: Overall Program Organization and Preliminaries
• Lab 2: Basic Solutions: Recursion and Iteration (this page)
• Lab 3: Specifying racquetball/volleyball and number of games in Class variables
• Lab 4: Class-level Boolean variables for tracing
• Lab 5: Command-line Arguments
• Table of Programs

Discussion: Flow of a Single Game of Racquetball or Volleyball

While details of a game may be handled in many ways, it is natural to use the flow of a game to structure the code. Ignoring initialization, there are two basic approaches:

• Game Flow 1: Proceed serve by serve until someone wins

         Serve
            if server wins volley
                score a point
                if server wins game
                     report winner
                else
                     same server serves again
            else
                other team  serves
  

• Game Flow 2: Game proceeds with the sequence A serves, then B serves

         Continue until someone wins
            A.  A serves until A wins game or loses serve
            B.  If A has not won
                    B serves until B winds game or loses serve
  

Determining Which Team Wins a Volley

In moving from high-level design to an implementation, an important consideration involves how to work with probabilities. Winning a serve depends upon the probability for that team. Suppose probAWin and probBWin are the probabilities that A and B, respectively, win a volley. For every volley, either A or B will win, so probAWin + probBWin = 1.0. To simulate winning a volley, we can use the function random() that returns numbers between 0.0 and 1.0 with approximately equal probability. In particular, the test random() < probAWin will be true the fraction of time specified by probAWin.

Game Flow 1: Serve-by-Serve Processing

In Game Flow 1, processing proceeds serve by serve until one team wins. Within a program, the flow from one serve to the next may be done in either of two main ways: recursion or iteration.

Serve-to-Serve Flow through Recursion

When implementing this approach recursively, we utilize parameters for the scores and probabilities and call the method with the correct values. When implementing this approach iteratively, we need separate variables for the server and receiver, the values need to be swapped when the serve changes, and an outer loop indicates that the volleys continue until the game is won.

The recursive is particularly simple and intuitive according to the outline. In the recursive approach, initialization of scores and server is accomplished in the initial call:

    playUntilWin ("A", "B", probWinVolley, 0, 0)

The recursive method for Game Approach 1 follows:

    /**
     * Play one game of racquetball or volleyball to conclusion
     * @parms  server and receiver indicate the team "A" or "B"
     *         probWinVolley specifies the likelihood the 
     *             server wins a volley
     *         serverScore, recScore contain current score of
     *             server and receiver
     * @returns winner of game: either "A" or "B"
     */
    public String playUntilWin (String server, String receiver,
          				     double probWinVolley, 
    					     int serverScore, int recScore) 
    {   // serve
        if (Math.random() < probWinVolley)
        {   // score point
    	   serverScore++;
    	   // if win, return winner
    	   if ((serverScore >= 15)
    		 && ((! winByTwo)
    		      || (serverScore >= recScore + 2)))
    	       return server;
    	    // if not win, serve again
    	    else
               return playUntilWin (server, receiver, probWinVolley, 
    				      serverScore, recScore);
    	}
    	else
    	{  // other side wins; other player serves 
    	   return playUntilWin (receiver, server, 1.0-probWinVolley,
    				     recScore, serverScore);
    	}
    }

In this recursive approach, method playUntilWin assumes the server, receiver, probabilities, and scores are established before a serve is to take place, and the method is responsible for handling the details of a single serve.

Program Game1Recur.java provides the full code for a simulation using Game Flow 1 with recursion.

Serve-to-Serve Flow through Iteration

When processing uses iterative to proceed from serve to serve, separate variables are needed to keep track of who the server is and what points and probabilities are associated with each team.

When using loops, it is helpful to identify a loop invariant that describes the state of each variable just before a serve takes place:

   serverScore      // variable indicates the current score for the server
   receiverScore    // variable indicates the current score receiving team
   server           // the team currently serving ("A" or "B")
   receiver         // the team receiving the serve ("B" or "A")
   probWinVolley    // probability that the server will win a volley

The initial probability for Team A is specified in the method's parameters. Otherwise, initialization within playUntilWin establishes the loop invariants for the first time the loop is executred.

  //  start at 0-0
   int serverScore = 0;     // the current score for the server
   int receiverScore = 0;   // the current score for the team receiving the serve
   String server = "A";     // "A" always serves first in the simulation
   String receiver = "B";   // "B" always receives the first serve

Processing in the main loop examines the results of the serve to determine if the server scores a point or if the serve changes. The main work of the loop, then, is to update variables, so that the above loop invariants are maintained for when the loop starts the next time. In the process, a temp variable may be needed as values are swapped. The loop terminates when one team wins.

Code for a full iterative simulation of a game follows:

    /**
     * Play one game of racquetball or volleyball to conclusion
     * @parms  probWinVolley specifies the likelihood the 
     *            server wins a volley
     * @returns winner of game: either "A" or "B"
     */
    public String playUntilWin (double probWinVolley) 
    {  //  start at 0-0
       int serverScore = 0;
       int receiverScore = 0;
       int tempScore;
       String server = "A";
       String receiver = "B";
       String temp;
    
       // continue indefinitely until server wins 
       while (true)
       {   // server serves
    	   if (Math.random() < probWinVolley)
    	   {   // server wins volley
    		serverScore++;
    
    		// check if server wins
    		if ((serverScore >= 15)
    	            && ((! winByTwo)
    			     || serverScore >= receiverScore + 2))
    		   return server;
    	   }
    	   else
    	   {  // swap information for server and receiver
    	      tempScore = serverScore;
    	      serverScore = receiverScore;
    	      receiverScore = tempScore;
    
    	      temp = server;
    	      server = receiver;
    	      receiver = temp;
    
    	      probWinVolley = 1.0 - probWinVolley;
    	   }
        } 
    }

Program Game1Iter1.java provides the full code for a simulation using Game Flow 1 with iteration.

Game Flow 2: Processing with the sequence: A Serves then B Serves

Turning to Game Approach 2, the phrase "A serves until A wins" translates naturally into a while loop. Processing to handle B's serve can proceed naturally with either recursion or iteration.

In the fully-iterative approach, the translation of the full outline can seem somewhat verbose if auxiliary methods are not used. Here is a sample iterative solution for Game Flow 2:

    /**
     * Play one game of racquetball or volleyball to conclusion
     * @parms  probWinVolley specifies the likelihood 
     *               the server wins a volley
     * @returns winner of game: either "A" or "B"
     */
     public String playUntilWin (double probWinVolley)
     {   //  start at 0-0                 
         int AScore = 0;
         int BScore = 0;
    
         // continue indefinitely              
         // (until A wins after A's serve or B wins after B's serve)
         while (true)
             {   // A serves              
                 while (Math.random() < probWinVolley)
                    {  AScore++;
                        if ((AScore >= 15)
                            && ((! winByTwo)
                                || (AScore >= BScore + 2)))
                            return "A";
                    }
    
                 // B serves               
                 while (Math.random() < 1.0 - probWinVolley)
                    {  BScore++;
                       if ((BScore >= 15)
                           && ((! winByTwo)
                               || (BScore >= AScore + 2)))
                          return "B";
                    }
             }
     }

Program Game1Iter2.java provides the full code for a simulation using Game Flow 2 with iteration (but without helper functions).

As an alternative, separate methods can be defined for the details of serving and winning. This clarifies the main method for playing the game, although the overall code for the game and its helper methods is somewhat longer.

    /**                            
     * Determine if player with first score has won       
     * @parms firstScore, secondScore are scores of 
     *            opposing players/teams          
     * @returns true if player with first score has won; 
     *            false otherwise            
     */
    public boolean won (int firstScore, int secondScore)
    {   // check if first person has won                
        return ((firstScore >= 15)
                && ((! winByTwo)
                    || (firstScore >= secondScore + 2)));
    }

    /**                  
     * allows player with first score to continue serving,  
     * until player has won game or lost volley        
     * @parms probWinVolley is probability that player 
     *             with first score wins volley        
     *        firstScore, secondScore are scores of 
     *             the two players/teams       
     * @returns final score of server 
     */
    public int serve (double probWinVolley, 
                      int firstScore, int secondScore)
    {   while (Math.random() < probWinVolley)
            {  firstScore++;
               if (won (firstScore, secondScore))
                   break;
            }
        return firstScore;
    }

   /**                                                    
     * Play one game of racquetball or volleyball to conclusion
     * @parms  probWinVolley specifies the likelihood the 
     *            server wins a volley      
     * @returns winner of game: either "A" or "B"         
     */
    public String playUntilWin (double probWinVolley)
    { //  start at 0-0
      int AScore = 0;
      int BScore = 0;

      // continue indefinitely                                  
      //(until A wins after A's serve or B wins after B's serve)
      while (true)
         {  // A serves                           
            AScore = serve (probWinVolley, AScore, BScore);
            // stop if A has won                           
            if (won (AScore, BScore))
                return "A";
            // B serves       
            BScore = serve (1.0-probWinVolley, BScore, AScore);
            // stop if B has won     
            if (won (BScore, AScore))
               return "B";
       }
    }

Program Game1Iter2Alt.java provides the full code for a simulation using Game Flow 2 with iteration and helper functions.

Comparing Code for Game Flow 1 and 2 and for Recursion and Iteration

The following table presents the lines of code for playing a game according to each game flow and the file name for the full program.

Approach	Lines for game method, including comments and formatting (from actual program)	Lines for game method, excluding comments and formatting	File name of actual program
Game Flow 1, Recursive	33 lines	20 lines	Game1Recur.java
Game Flow 1, Iterative	45 lines	27 lines	Game1Iter1.java
Game Flow 2, Iterative, no helper methods	34 lines	21 lines	Game1Iter2.java
Game Flow 2, Iterative with helper methods	57 lines (with helper functions)	26 lines (with helper functions)	Game1Iter2Alt.java

For each of these programs, the code to print headings, iterate over the probabilities, and iterate for 1000 games has about the same size N 120 lines (for game approach 1) or 121 lines (for game approach 2), including comments. (Approach 2 has an extra line of initial comments.)

Steps for this Lab

1. Review each of the four program variations discussed in this Lab:

   • Game1Recur.java: Game flow 1 with recursion
   • Game1Iter1.java: Game flow 1 with iteration
   • Game1Iter2.java: Game flow 2 with iteration (no helper functions)
   • Game1Iter2Alt.java: Game flow 2 with iteration and helper functions

   Compare and contrast these problem-solving approaches and their resulting programs.

   1. What are the relative advantages or disadvantages of each approach
   2. How readable and natural is each solution?
   3. Could each solution be made shorter, clearer, etc.?

2. Program Game1Iter2Alt.java uses two helper methods, won and serve.

   1. Why do you think that neither of these methods are declared as static?
   2. Could either or both of these methods be declared static? Explain.

3. The solutions given above for Game Flow 2 are all iterative. However, recursion might be used in either of two ways:

   • Recursion might be used for repetition in the outer loop (that is, the body of a method would contain the elements, "A serves; if A has not won, B serves").
   • Recursion might be used for repetitions when "A serves" or when "B serves" (that is, recursion could replace an inner loop).

   Consider how recursion might be used in place of iteration in Game Flow 2.

   1. Discuss the relative advantages of using recursion versus iteration in each of these circumstances.
   2. Revise one of the iterative solutions for Game Flow 2 to use recursion rather than iteration for at least one of the outer or inner loops.

4. How might the simulations be modified so that A's probability of winning a volley could be different if A serves or if B serves? Choose one of the Java programs from Step 1, and modify it so that

   • One field or variable contains the probabilty that A will win a volley when A is serving, and
   • Another field contains the probabuility that A will win a volley when B is serving.

5. As stated, these simulation programs specify the same probabilty of A winning a volley, regardless of who is serving. (E.g., A wins 40% of the serves, when either A or B serves.)

   Review the simulations presented and identify the assumptions that are being made throughout the code. To what extent are these assumptions realistic?

     http://www.walker.cs.grinnell.edu/apcsa/racquetball/lab-recursion-iteration.shtml