11-loop.html


<!doctype html>
<html lang="en" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      
      
        <link rel="canonical" href="https://nus-cs1010.github.io/2021-s1/11-loop.html">
      
      
      <link rel="shortcut icon" href="assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1.2, mkdocs-material-6.0.2">
    
    
        <title>11. Loops - CS1010 Programming Methodology</title>
      
    
      <link rel="stylesheet" href="assets/stylesheets/main.38780c08.min.css">
      
        
        <link rel="stylesheet" href="assets/stylesheets/palette.3f72e892.min.css">
        
          
          <meta name="theme-color" content="#009485">
        
      
        <link href="https://fonts.gstatic.com" rel="preconnect" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto",-apple-system,BlinkMacSystemFont,Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono",SFMono-Regular,Consolas,Menlo,monospace}</style>
      
    
      <link rel="stylesheet" href="stylesheets/extra.css">
    
      <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:400,700">
    
      <link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Lora:ital,wght@0,400;0,500;0,600;0,700;1,400;1,500;1,600;1,700&display=swap">
    
    
  </head>
  
  
    <body dir="ltr" data-md-color-scheme="" data-md-color-primary="teal" data-md-color-accent="">
      
  
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" for="__drawer"></label>
    <div data-md-component="skip">
      
        
        <a href="#unit-11-loops" class="md-skip">
          Skip to content
        </a>
      
    </div>
    <div data-md-component="announce">
      
    </div>
    
      <header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid" aria-label="Header">
    <a href="https://nus-cs1010.github.io/2021-s1" title="CS1010 Programming Methodology" class="md-header-nav__button md-logo" aria-label="CS1010 Programming Methodology">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 003-3 3 3 0 00-3-3 3 3 0 00-3 3 3 3 0 003 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54z"/></svg>

    </a>
    <label class="md-header-nav__button md-icon" for="__drawer">
      <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M3 6h18v2H3V6m0 5h18v2H3v-2m0 5h18v2H3v-2z"/></svg>
    </label>
    <div class="md-header-nav__title" data-md-component="header-title">
      
        <div class="md-header-nav__ellipsis">
          <span class="md-header-nav__topic md-ellipsis">
            CS1010 Programming Methodology
          </span>
          <span class="md-header-nav__topic md-ellipsis">
            
              11. Loops
            
          </span>
        </div>
      
    </div>
    
      <label class="md-header-nav__button md-icon" for="__search">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0116 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.516 6.516 0 019.5 16 6.5 6.5 0 013 9.5 6.5 6.5 0 019.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5z"/></svg>
      </label>
      
<div class="md-search" data-md-component="search" role="dialog">
  <label class="md-search__overlay" for="__search"></label>
  <div class="md-search__inner" role="search">
    <form class="md-search__form" name="search">
      <input type="text" class="md-search__input" name="query" aria-label="Search" placeholder="Search" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="search-query" data-md-state="active">
      <label class="md-search__icon md-icon" for="__search">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0116 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.516 6.516 0 019.5 16 6.5 6.5 0 013 9.5 6.5 6.5 0 019.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5z"/></svg>
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
      </label>
      <button type="reset" class="md-search__icon md-icon" aria-label="Clear" data-md-component="search-reset" tabindex="-1">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M19 6.41L17.59 5 12 10.59 6.41 5 5 6.41 10.59 12 5 17.59 6.41 19 12 13.41 17.59 19 19 17.59 13.41 12 19 6.41z"/></svg>
      </button>
    </form>
    <div class="md-search__output">
      <div class="md-search__scrollwrap" data-md-scrollfix>
        <div class="md-search-result" data-md-component="search-result">
          <div class="md-search-result__meta">
            Initializing search
          </div>
          <ol class="md-search-result__list"></ol>
        </div>
      </div>
    </div>
  </div>
</div>
    
    
  </nav>
</header>
    
    <div class="md-container" data-md-component="container">
      
      
      <main class="md-main" data-md-component="main">
        <div class="md-main__inner md-grid">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    <nav class="md-nav md-nav--primary" aria-label="Navigation" data-md-level="0">
  <label class="md-nav__title" for="__drawer">
    <a href="https://nus-cs1010.github.io/2021-s1" title="CS1010 Programming Methodology" class="md-nav__button md-logo" aria-label="CS1010 Programming Methodology">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 003-3 3 3 0 00-3-3 3 3 0 00-3 3 3 3 0 003 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54z"/></svg>

    </a>
    CS1010 Programming Methodology
  </label>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
  <li class="md-nav__item">
    <a href="index.html" class="md-nav__link">
      Home
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="midterm.html" class="md-nav__link">
      Midterm
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="final.html" class="md-nav__link">
      Final
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="pe1.html" class="md-nav__link">
      PE1
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="pe2.html" class="md-nav__link">
      PE2
    </a>
  </li>

    
  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-6" type="checkbox" id="nav-6">
    
    <label class="md-nav__link" for="nav-6">
      General
      <span class="md-nav__icon md-icon"></span>
    </label>
    <nav class="md-nav" aria-label="General" data-md-level="1">
      <label class="md-nav__title" for="nav-6">
        <span class="md-nav__icon md-icon"></span>
        General
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
  <li class="md-nav__item">
    <a href="about.html" class="md-nav__link">
      About CS1010
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="outcomes.html" class="md-nav__link">
      Learning Outcomes
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="schedule.html" class="md-nav__link">
      Schedule
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="accounts.html" class="md-nav__link">
      Accounts
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="policies.html" class="md-nav__link">
      Policies
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  <li class="md-nav__item md-nav__item--active md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-7" type="checkbox" id="nav-7" checked>
    
    <label class="md-nav__link" for="nav-7">
      Notes
      <span class="md-nav__icon md-icon"></span>
    </label>
    <nav class="md-nav" aria-label="Notes" data-md-level="1">
      <label class="md-nav__title" for="nav-7">
        <span class="md-nav__icon md-icon"></span>
        Notes
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
  <li class="md-nav__item">
    <a href="01-program.html" class="md-nav__link">
      1. What is a Program?
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="02-algo.html" class="md-nav__link">
      2. Computational Problem & Algorithms
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="03-func.html" class="md-nav__link">
      3. Functions
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="04-type.html" class="md-nav__link">
      4. Types
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="05-first-c.html" class="md-nav__link">
      5. First C Program
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="06-cs1010-io.html" class="md-nav__link">
      6. CS1010 I/O Library
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="07-arithmetic-ops.html" class="md-nav__link">
      7. Arithmetic Operations
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="08-if-else.html" class="md-nav__link">
      8. Conditionals
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="09-logical-exp.html" class="md-nav__link">
      9. Logical Expressions
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="10-assert.html" class="md-nav__link">
      10. Assertion
    </a>
  </li>

        
  <li class="md-nav__item md-nav__item--active">
    
    <input class="md-nav__toggle md-toggle" data-md-toggle="toc" type="checkbox" id="__toc">
    
      
      <label class="md-nav__link md-nav__link--active" for="__toc">
        11. Loops
        <span class="md-nav__icon md-icon"></span>
      </label>
    
    <a href="11-loop.html" class="md-nav__link md-nav__link--active">
      11. Loops
    </a>
    
      
<nav class="md-nav md-nav--secondary" aria-label="Table of contents">
  
  
    <label class="md-nav__title" for="__toc">
      <span class="md-nav__icon md-icon"></span>
      Table of contents
    </label>
    <ul class="md-nav__list" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#learning-objectives" class="md-nav__link">
    Learning Objectives
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#writing-loops" class="md-nav__link">
    Writing Loops
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#a-for-loop" class="md-nav__link">
    A for loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#while-loop" class="md-nav__link">
    while Loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#a-do-while-loop" class="md-nav__link">
    A do-while loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#example-guess-a-number" class="md-nav__link">
    Example: Guess a Number
  </a>
  
    <nav class="md-nav" aria-label="Example: Guess a Number">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#answering-the-four-questions" class="md-nav__link">
    Answering The Four Questions
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#designing-the-flowchart" class="md-nav__link">
    Designing the Flowchart
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#the-c-code" class="md-nav__link">
    The C code
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
        <li class="md-nav__item">
  <a href="#infinite-loop" class="md-nav__link">
    Infinite Loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#problem-set" class="md-nav__link">
    Problem Set
  </a>
  
    <nav class="md-nav" aria-label="Problem Set">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#problem-111" class="md-nav__link">
    Problem 11.1
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#problem-112" class="md-nav__link">
    Problem 11.2
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#problem-113" class="md-nav__link">
    Problem 11.3
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
    </ul>
  
</nav>
    
  </li>

        
  <li class="md-nav__item">
    <a href="12-invariant.html" class="md-nav__link">
      12. Loop Invariant
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="13-call-stack.html" class="md-nav__link">
      13. Call Stack
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="14-pointers.html" class="md-nav__link">
      14. Memory Addresses
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="15-array.html" class="md-nav__link">
      15. Array
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="16-string.html" class="md-nav__link">
      16. String
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="17-call-by-reference.html" class="md-nav__link">
      17. Call by Reference
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="18-heap.html" class="md-nav__link">
      18. Heap
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="19-md-array.html" class="md-nav__link">
      19. Multi-dimensional Arrays
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="20-macro.html" class="md-nav__link">
      20. C Preprocessing
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="21-assert.html" class="md-nav__link">
      21. The assert macro
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="22-efficiency.html" class="md-nav__link">
      22. Efficiency
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="23-search.html" class="md-nav__link">
      23. Searching
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="24-sort.html" class="md-nav__link">
      24. Sorting
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="25-tower.html" class="md-nav__link">
      25. Tower of Hanoi
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="26-permutation.html" class="md-nav__link">
      26. Permutation
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="27-queens.html" class="md-nav__link">
      27. N Queens
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="28-struct.html" class="md-nav__link">
      28. Struct
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="29-stdio.html" class="md-nav__link">
      29. Standard I/O
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-8" type="checkbox" id="nav-8">
    
    <label class="md-nav__link" for="nav-8">
      Exercises
      <span class="md-nav__icon md-icon"></span>
    </label>
    <nav class="md-nav" aria-label="Exercises" data-md-level="1">
      <label class="md-nav__title" for="nav-8">
        <span class="md-nav__icon md-icon"></span>
        Exercises
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
  <li class="md-nav__item">
    <a href="ex00.html" class="md-nav__link">
      0. Echo, Divide, Quadratic
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="ex01.html" class="md-nav__link">
      1. GCD, Day, Leap
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="ex02.html" class="md-nav__link">
      2. Binary, Rectangle, Fibonacci
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="ex03.html" class="md-nav__link">
      3. Weekday, Circle, Histogram
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="ex04.html" class="md-nav__link">
      4. Fill, Sudoku
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-9" type="checkbox" id="nav-9">
    
    <label class="md-nav__link" for="nav-9">
      Assignments
      <span class="md-nav__icon md-icon"></span>
    </label>
    <nav class="md-nav" aria-label="Assignments" data-md-level="1">
      <label class="md-nav__title" for="nav-9">
        <span class="md-nav__icon md-icon"></span>
        Assignments
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
  <li class="md-nav__item">
    <a href="assignment.html" class="md-nav__link">
      Overview
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as01.html" class="md-nav__link">
      1. Box, Digits, Suffix, Taxi
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as02.html" class="md-nav__link">
      2. Collatz, Triangle, Prime, Pattern
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as03.html" class="md-nav__link">
      3. ID, Kendall, Max, CountingSort
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as04.html" class="md-nav__link">
      4. SelectionSort, Mastermind
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as05.html" class="md-nav__link">
      5. Contact, Social, Life
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as06.html" class="md-nav__link">
      6. Add, Frequency, Permutation
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as07.html" class="md-nav__link">
      7. Peak, Sort, Inversion
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as08.html" class="md-nav__link">
      8. Walk, Maze
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="as09.html" class="md-nav__link">
      9. Digits
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  <li class="md-nav__item">
    <a href="readings.html" class="md-nav__link">
      Readings
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="c-in-cs1010.html" class="md-nav__link">
      C in CS1010
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="library.html" class="md-nav__link">
      CS1010 I/O Library
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="style.html" class="md-nav__link">
      C Style Convention
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="documentation.html" class="md-nav__link">
      C Documentation Guide
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="messages.html" class="md-nav__link">
      Compiler Messages
    </a>
  </li>

    
  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-16" type="checkbox" id="nav-16">
    
    <label class="md-nav__link" for="nav-16">
      Software/Tools
      <span class="md-nav__icon md-icon"></span>
    </label>
    <nav class="md-nav" aria-label="Software/Tools" data-md-level="1">
      <label class="md-nav__title" for="nav-16">
        <span class="md-nav__icon md-icon"></span>
        Software/Tools
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
  <li class="md-nav__item">
    <a href="environments.html" class="md-nav__link">
      Programming Environments
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="unix.html" class="md-nav__link">
      UNIX
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="clang.html" class="md-nav__link">
      CLang
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="vim.html" class="md-nav__link">
      Vim
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="tmate.html" class="md-nav__link">
      TMate
    </a>
  </li>

        
  <li class="md-nav__item">
    <a href="zoom.html" class="md-nav__link">
      Zoom
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  <li class="md-nav__item">
    <a href="archive.html" class="md-nav__link">
      Older Announcements
    </a>
  </li>

    
  <li class="md-nav__item">
    <a href="1819s1.html" class="md-nav__link">
      18/19 Sem 1
    </a>
  </li>

    
  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
              <div class="md-sidebar md-sidebar--secondary" data-md-component="toc">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    
<nav class="md-nav md-nav--secondary" aria-label="Table of contents">
  
  
    <label class="md-nav__title" for="__toc">
      <span class="md-nav__icon md-icon"></span>
      Table of contents
    </label>
    <ul class="md-nav__list" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#learning-objectives" class="md-nav__link">
    Learning Objectives
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#writing-loops" class="md-nav__link">
    Writing Loops
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#a-for-loop" class="md-nav__link">
    A for loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#while-loop" class="md-nav__link">
    while Loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#a-do-while-loop" class="md-nav__link">
    A do-while loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#example-guess-a-number" class="md-nav__link">
    Example: Guess a Number
  </a>
  
    <nav class="md-nav" aria-label="Example: Guess a Number">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#answering-the-four-questions" class="md-nav__link">
    Answering The Four Questions
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#designing-the-flowchart" class="md-nav__link">
    Designing the Flowchart
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#the-c-code" class="md-nav__link">
    The C code
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
        <li class="md-nav__item">
  <a href="#infinite-loop" class="md-nav__link">
    Infinite Loop
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#problem-set" class="md-nav__link">
    Problem Set
  </a>
  
    <nav class="md-nav" aria-label="Problem Set">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#problem-111" class="md-nav__link">
    Problem 11.1
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#problem-112" class="md-nav__link">
    Problem 11.2
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#problem-113" class="md-nav__link">
    Problem 11.3
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
    </ul>
  
</nav>
                  </div>
                </div>
              </div>
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                <h1 id="unit-11-loops">Unit 11: Loops</h1>
<h2 id="learning-objectives">Learning Objectives</h2>
<p>After this unit, students should:</p>
<ul>
<li>be able to identify the four components of a loop: initialization, body, update, and condition</li>
<li>be able to express a computational solution as a loop with the four components above</li>
<li>be able to implement a loop using either the <code>for</code>, <code>while</code> or <code>do-while</code> construct in C</li>
<li>be able to trace through the control flows of each loop construct</li>
<li>understand the correspondence between the different loop constructs</li>
<li>be aware of the "infinite loops" bug, what causes it, and what to pay attention to avoid it.</li>
</ul>
<p>In <a href="08-if-else.html">Unit 8</a>, you were introduced to writing code that follows one of two possible execution paths using the <code>if</code>-<code>else</code> statements, using a logical expression to decide which path to take.</p>
<p>Sometimes, we want to execute one of the branches repeatedly (or iteratively), over-and-over again, until a certain logical condition is met.  You have seen this construct in the <span class="arithmatex">\(max\)</span> and <span class="arithmatex">\(sum\)</span> example, where we repeatedly go through the numbers in the list until <span class="arithmatex">\(i == k\)</span>.</p>
<h2 id="writing-loops">Writing Loops</h2>
<p>To write a loop, we need to think about the following four questions:</p>
<ul>
<li>what do we want to do repeatedly?</li>
<li>what do we need to set up before repeating the above?</li>
<li>what changes from one repetition to another?  </li>
<li>how to decide if we should stop repeating (or conversely, to continue repeating?)</li>
</ul>
<p>There is a fifth question that is as important as the above but is harder to answer (and not necessary for writing simple loops), so we will leave it to <a href="12-invariant.html">Unit 12</a>.</p>
<p>Let's revisit the example of <code>max</code>.  Here is the answer to the four questions:</p>
<ul>
<li>
<p>What do we want to do repeatedly?  We want to compare the element <span class="arithmatex">\(l_i\)</span> to <span class="arithmatex">\(m\)</span>, and update <span class="arithmatex">\(m\)</span> to <span class="arithmatex">\(l_i\)</span> if <span class="arithmatex">\(l_i &gt; m\)</span>.</p>
</li>
<li>
<p>What do we need to set up before repeating the above?  We need to have some initial value of <span class="arithmatex">\(m\)</span> and <span class="arithmatex">\(i\)</span>.  We set it up as <span class="arithmatex">\(m = l_0\)</span> and <span class="arithmatex">\(i = 1\)</span>.</p>
</li>
<li>
<p>What would be different each time we repeat the above?  Every time we repeat, <span class="arithmatex">\(i\)</span> will be different.  To be more precise, <span class="arithmatex">\(i\)</span> is one more than before.</p>
</li>
<li>
<p>How to decide if we should continue repeating the above?  We stop when there is no more element to compare, i.e., <span class="arithmatex">\(i\)</span> equals <span class="arithmatex">\(k\)</span>.  In other words, we continue if <span class="arithmatex">\(i &lt; k\)</span>.</p>
</li>
</ul>
<p><img alt="max" src="figures/max-flowchart/max-flowchart.001.png" /></p>
<p>Let's consider another example.  We have seen how to compute factorial recursively.  Let's try to compute factorial using a loop.</p>
<p>Recall that <span class="arithmatex">\(n! = n \times n-1 \times n-2 .. 2 \times 1\)</span>.  Given <span class="arithmatex">\(n\)</span>, how do we find <span class="arithmatex">\(n!\)</span> using a loop?  </p>
<p>The idea to solve this with a loop is to start with the value <span class="arithmatex">\(n\)</span>, and repeatedly multiply another value <span class="arithmatex">\(i\)</span>, starting with <span class="arithmatex">\(i = n - 1\)</span>, then <span class="arithmatex">\(i = n - 2\)</span>, etc, until <span class="arithmatex">\(i = 2\)</span>.  We do not need to multiple with <span class="arithmatex">\(i = 1\)</span> since it does not change the value.</p>
<p>Like any other problem, we need to consider what are the variables we need to maintain.  In this case, we should maintain the partial product of the factorial and a variable <span class="arithmatex">\(i\)</span> that corresponds to value to multiple into the partial product.</p>
<ul>
<li>What do we want to do repeatedly?  Multiply <span class="arithmatex">\(i\)</span> into the partial product.</li>
<li>What do we need to set up before repeating the above?  We set up the partial product to be <span class="arithmatex">\(n\)</span> and <span class="arithmatex">\(i\)</span> to be <span class="arithmatex">\(n - 1\)</span>.</li>
<li>What changes from one repetition to another?  <span class="arithmatex">\(i\)</span> would decrease by one every time we repeat the above.</li>
<li>How to decide if we should stop repeating (or conversely, to continue repeating?)  We can stop when we have multiplied <span class="arithmatex">\(i = 2\)</span> to the partial product.</li>
</ul>
<p>We can express the algorithm above using the following flowchart:</p>
<p><img alt="factorial" src="figures/loops/loops.004.png" /></p>
<h2 id="a-for-loop">A <code>for</code> loop</h2>
<p>Now that we have seen the four essential elements of a <code>for</code> loop, let's write some loops in C.</p>
<p>C provides three ways to write a loop.  Let's start with a simple one:  the <code>for</code> loop.  </p>
<p>The <code>for</code> loop in C has the following syntax:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>1
2
3</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="k">for</span> <span class="p">(</span><span class="o">&lt;</span><span class="n">initialize</span><span class="o">&gt;</span><span class="p">;</span> <span class="o">&lt;</span><span class="n">condition</span><span class="o">&gt;</span><span class="p">;</span> <span class="o">&lt;</span><span class="n">update</span><span class="o">&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="o">&lt;</span><span class="n">body</span><span class="o">&gt;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>There are four components, corresponding to the four questions above:</p>
<ul>
<li>The <code>initialize</code> statement sets up the loop (i.e., "What do we need to set up before repeating the above?").  </li>
<li>The <code>condition</code> statement indicates when we should stop repeating.  If it evaluates to <code>true</code>, it will cause the loop to continue, otherwise, the loop stops.</li>
<li>The <code>update</code> statement is executed after every loop.  (i.e., "What changes from one repetition to another?")</li>
<li>The <code>body</code> statement is the action that we want to do repeatedly.  </li>
</ul>
<p><img alt="for" src="figures/loops/loops.003.png" /></p>
<p>For the <code>initialize</code> and <code>update</code> statement, even though C allows us to include multiple initializations and multiple updates, it makes the code harder to read and understand.  C also allows us to have empty statements for <code>initialize</code>, <code>condition</code> and/or <code>update</code>.  As such, in CS1010, we will stick to performing one initialization and one update only.</p>
<p>For example, in the setup phase for factorial, we should initialize the partial product to <span class="arithmatex">\(n\)</span> and <span class="arithmatex">\(i\)</span> to <span class="arithmatex">\(n - 1\)</span>, that's two assignments.  We commonly choose the index which we increment or decrement as we loop, hence we choose to initialize <span class="arithmatex">\(i\)</span> in the <code>initialize</code> statement of the <code>for</code> loop, and leave the initialization of <code>product</code> to a separate assignment before the <code>for</code> loop.</p>
<p>Here is an example on computing the factorial with a for loop:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>1
2
3
4
5
6
7
8</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="kt">long</span> <span class="nf">factorial</span><span class="p">(</span><span class="kt">long</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="kt">long</span> <span class="n">product</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">product</span> <span class="o">*=</span> <span class="n">i</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">product</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>The code above is almost correct.  We only need to handle the special case when <code>n</code> is 0.  The complete code for the function is thus:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="kt">long</span> <span class="nf">factorial</span><span class="p">(</span><span class="kt">long</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">long</span> <span class="n">product</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">n</span><span class="mi">-1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">product</span> <span class="o">*=</span> <span class="n">i</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">product</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<h2 id="while-loop"><code>while</code> Loop</h2>
<p>The second way to write a loop in C is to use a <code>while</code> loop.  The while loop looks like this:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>1
2
3</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="k">while</span> <span class="p">(</span><span class="o">&lt;</span><span class="n">condition</span><span class="o">&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="o">&lt;</span><span class="n">body</span><span class="o">&gt;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>The statements in <code>&lt;body&gt;</code> will be executed if <code>&lt;condition&gt;</code> is true.  </p>
<p>Note that the syntax of the <code>while</code> loop above does not contain the <code>&lt;initialize&gt;</code> and the <code>&lt;update&gt;</code> component.  When we write the loop, however, we still need to think about them, and add them to the appropriate place in the code, as follows:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>1
2
3
4
5</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="o">&lt;</span><span class="n">initialize</span><span class="o">&gt;</span>
<span class="k">while</span> <span class="p">(</span><span class="o">&lt;</span><span class="n">condition</span><span class="o">&gt;</span><span class="p">)</span> <span class="p">{</span>
    <span class="o">&lt;</span><span class="n">body</span><span class="o">&gt;</span>
    <span class="o">&lt;</span><span class="n">update</span><span class="o">&gt;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>The corresponding flowchart for <code>while</code> is:</p>
<p><img alt="for" src="figures/loops/loops.003.png" /></p>
<p>Compare the flowchart for <code>while</code> to the flowchart for <code>for</code> earlier.  You will see that they are the same!</p>
<p>Here is the <code>while</code> version of the <code>factorial</code> function:
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="kt">long</span> <span class="nf">factorial</span><span class="p">(</span><span class="kt">long</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">long</span> <span class="n">product</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
    <span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">product</span> <span class="o">*=</span> <span class="n">i</span><span class="p">;</span>
        <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">product</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table></p>
<p>In the <code>while</code> loop, however, we can be more flexible in terms of what we want to do inside the loop.  Technically, there is no difference between <code>update</code> and <code>body</code> since they are just a bunch of C statements.  We can interleave <code>&lt;update&gt;</code> and <code>&lt;body&gt;</code> or execute <code>&lt;update&gt;</code> first before <code>&lt;body&gt;</code>, depending on the algorithm.  With <code>for</code> loop, there is no such flexibility as <code>&lt;update&gt;</code> has to be executed after <code>&lt;body&gt;</code>.</p>
<h2 id="a-do-while-loop">A <code>do-while</code> loop</h2>
<p>The third way we can write a loop in C is to use a <code>do-while</code> loop.  The <code>do-while</code> loop is very similar to <code>while</code>, except that the body of the loop is guaranteed to be executed at least once.  </p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>1
2
3
4
5</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="o">&lt;</span><span class="n">initialize</span><span class="o">&gt;</span>
<span class="k">do</span> <span class="p">{</span>
    <span class="o">&lt;</span><span class="n">body</span><span class="o">&gt;</span>
    <span class="o">&lt;</span><span class="n">update</span><span class="o">&gt;</span>
<span class="p">}</span> <span class="k">while</span> <span class="p">(</span><span class="o">&lt;</span><span class="n">condition</span><span class="o">&gt;</span><span class="p">);</span>
</code></pre></div>
</td></tr></table>
<p><img alt="for" src="figures/loops/loops.005.png" /></p>
<p>Similar to the <code>while</code> loop, the <code>&lt;body&gt;</code> component and <code>&lt;update&gt;</code> component in the loop do not have to be in order.</p>
<div class="admonition note">
<p>There is a semicolon <code>;</code> after a <code>do-while</code> loop.</p>
</div>
<p>Let's look at an example where using <code>do-while</code> is more natural than <code>while</code>.</p>
<h2 id="example-guess-a-number">Example: Guess a Number</h2>
<p>Let's write a program that plays a game with the user.  The program generates a random integer number between 1 and 100.  The user will guess what that number is.  If the user guesses correctly, the program congratulates the user.  Otherwise, the program tells the user whether the guess is too high or too low, and let the user guess again.  This process repeats until the guess is correct.</p>
<p>Note that, here, the user needs to guess at least once, so it is more natural to use a <code>do</code>-<code>while</code> loop than a <code>while</code> or a <code>for</code>.</p>
<h3 id="answering-the-four-questions">Answering The Four Questions</h3>
<ul>
<li>What do we want to do repeatedly?  We want to read the guess from the user and respond to the user.</li>
<li>What do we need to set up before repeating the above?  We need to generate a random integer between 1 and 100.</li>
<li>What changes from one repetition to another?  The guess <em>may</em> be different.</li>
<li>How to decide if we should continue repeating the above?  We stop when the guess is correct.</li>
</ul>
<h3 id="designing-the-flowchart">Designing the Flowchart</h3>
<p>Here is the flowchart of the steps described above.  </p>
<p><img alt="for" src="figures/loops/loops.006.png" /></p>
<h3 id="the-c-code">The C code</h3>
<p>The entire corresponding program is shown below:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span> 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</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="cp">#include</span> <span class="cpf">&lt;stdlib.h&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;sys/times.h&gt;</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&quot;cs1010.h&quot;</span><span class="cp"></span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
  <span class="c1">// Initialize the random number generator</span>
  <span class="n">srandom</span><span class="p">(</span><span class="n">times</span><span class="p">(</span><span class="mi">0</span><span class="p">));</span>

  <span class="c1">// Generate a random number between 1 and 100</span>
  <span class="kt">long</span> <span class="n">answer</span> <span class="o">=</span> <span class="p">(</span><span class="n">random</span><span class="p">()</span> <span class="o">%</span> <span class="mi">100</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>

  <span class="kt">long</span> <span class="n">guess</span><span class="p">;</span>
  <span class="k">do</span> <span class="p">{</span>
    <span class="c1">// Read guess and feedback to user</span>
    <span class="n">guess</span> <span class="o">=</span> <span class="n">cs1010_read_long</span><span class="p">();</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">guess</span> <span class="o">&gt;</span> <span class="n">answer</span><span class="p">)</span> <span class="p">{</span>
      <span class="n">cs1010_println_string</span><span class="p">(</span><span class="s">&quot;too high&quot;</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">guess</span> <span class="o">&lt;</span> <span class="n">answer</span><span class="p">)</span> <span class="p">{</span>
      <span class="n">cs1010_println_string</span><span class="p">(</span><span class="s">&quot;too low&quot;</span><span class="p">);</span>
    <span class="p">}</span>
  <span class="p">}</span> <span class="k">while</span> <span class="p">(</span><span class="n">guess</span> <span class="o">!=</span> <span class="n">answer</span><span class="p">);</span>

  <span class="c1">// { guess == answer }</span>
  <span class="n">cs1010_println_string</span><span class="p">(</span><span class="s">&quot;you got it.  congrats!&quot;</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>I will not go into details of what <code>srandom(times(0))</code> means.  You can look it up on your own if you are interested (InfoSec students may want to do this as generating a good random number is key to keeping systems secure).  </p>
<p>The function <code>random()</code> generates a random integer, which we limit to 0 to 99 by modulo-ing it with 100.  We then add 1 to it to a number between 1 and 100, inclusive.</p>
<h2 id="infinite-loop">Infinite Loop</h2>
<p>One of the common bugs that programmers encounter when writing loops is the <em>infinite loop</em>.  An infinite loop is a loop that never terminates until an external input (++control-c++) terminates the program.</p>
<p>Consider the slight variation of the <code>factorial</code> function below:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="kt">long</span> <span class="nf">factorial</span><span class="p">(</span><span class="kt">long</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">long</span> <span class="n">product</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
    <span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="mi">2</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">product</span> <span class="o">*=</span> <span class="n">i</span><span class="p">;</span>
        <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">product</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>What is the return value of <code>factorial(-2)</code>?  Take a moment to trace through the code.</p>
<p>The answer is that <code>factorial(-2)</code> will never return!  Since <code>i</code> is initialized to <code>-3</code> on Line 7, and <code>i</code> only get smaller every time Line 10 is called.  So, the terminating condition <code>i != 2</code> will never be true.  As a result, the loop never terminates.</p>
<p>Let's examine under what condition would a loop continue forever, using three of the loop components: <code>&lt;initialize&gt;</code>, <code>&lt;update&gt;</code>, and <code>&lt;condition&gt;</code>.  </p>
<p>Consider the variable(s) used in <code>&lt;condition&gt;</code> and the condition in which <code>&lt;condition&gt;</code> evaluates to <em>false</em>.  This is the <em>terminal state</em> of the loop.  Now consider how these variables are set up in <code>&lt;initialize&gt;</code>.  This is the <em>initial state</em>.  For the loop to terminate, the sequence of operations performed by the <code>&lt;update&gt;</code> component must transit these variables from the initial state to the terminal state.  Otherwise, the loop will never terminate.</p>
<p>As an example, let's consider what happens when we call <code>factorial(10)</code>.  The terminal state is <code>{ i == 2 }</code>.  The initial state is <code>{ i == 9 }</code>.  The update is performed by subtracting 1 from <code>i</code> in every loop.  So the value of <code>i</code> starts at 9, and it becomes 8, 7, 6, .. and eventually the condition <code>i == 2</code> will be true, <code>i != 2</code> will be false, and the loop terminates.</p>
<p>As an example, let's consider what happens when we call <code>factorial(-2)</code>.  The terminal state is <code>{ i == 2 }</code>.  The initial state is <code>{ i == -3 }</code>.  The update is performed by subtracting 1 from <code>i</code> in every loop.  So the value of <code>i</code> starts at -3, and it becomes -4, -5, -6, ...  The <code>&lt;update&gt;</code> condition is moving the state <em>away</em> from the terminal state.  So this loop never terminates!<sup id="fnref:1"><a class="footnote-ref" href="#fn:1">1</a></sup></p>
<p>To prevent the infinite loop bug, when developing your <code>&lt;initialize&gt;</code>, <code>&lt;update&gt;</code>, and <code>&lt;condition&gt;</code>, make sure that <code>&lt;update&gt;</code> always nudges the state from the initial state stated in <code>&lt;initialize&gt;</code> to the terminating condition specified by <code>&lt;condition&gt;</code> at each iteration and the terminal state is achievable eventually.</p>
<p>Now, consider the version of <code>factorial</code> where the terminating condition is <code>{ i &lt; 2 }</code>.  </p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="kt">long</span> <span class="nf">factorial</span><span class="p">(</span><span class="kt">long</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">long</span> <span class="n">product</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
    <span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">product</span> <span class="o">*=</span> <span class="n">i</span><span class="p">;</span>
        <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">product</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>This version does not have the possibility of an infinite loop.  Regardless of the initial state (i.e., regardless of what the value of <code>i</code> is initialized to), we will always reach the terminal state.</p>
<h2 id="problem-set">Problem Set</h2>
<h3 id="problem-111">Problem 11.1</h3>
<p>Here is another version of the <code>factorial</code> function:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span> 1
 2
 3
 4
 5
 6
 7
 8
 9
10</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="kt">long</span> <span class="nf">factorial</span><span class="p">(</span><span class="kt">long</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
    <span class="kt">long</span> <span class="n">product</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">product</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">product</span> <span class="o">*=</span> <span class="n">i</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">product</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>Does this code run correctly?  If it is incorrect, explain what is wrong and suggest a fix.  (Hint: translate this to the corresponding flowchart and trace through the flowchart).</p>
<h3 id="problem-112">Problem 11.2</h3>
<p>(a) Rewrite the "Guess A Number" program so that it shows the user the number of guesses made before the correct guess is entered.</p>
<p>(b) Rewrite the "Guess A Number" program with a <code>while</code> loop.</p>
<p>(c) Extend the "Guess A Number" program so that it plays the game for five rounds with the user, and at the end, shows the user the average number of guesses over five rounds.  (Hint: you should put the loop that reads the guess and prints feedback to the user into another function.)</p>
<p>(d) What is the optimal strategy to play the game?</p>
<h3 id="problem-113">Problem 11.3</h3>
<p>Trace the following algorithms:</p>
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>1
2
3
4
5
6
7
8
9</pre></div></td><td class="code"><div class="highlight"><pre><span></span><code><span class="kt">long</span> <span class="nf">mystery</span><span class="p">(</span><span class="kt">long</span> <span class="n">n</span><span class="p">,</span> <span class="kt">long</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">long</span> <span class="n">something</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
    <span class="kt">long</span> <span class="n">count</span> <span class="o">=</span> <span class="mi">-1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">something</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">something</span> <span class="o">/=</span> <span class="n">k</span><span class="p">;</span>
        <span class="n">count</span> <span class="o">+=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">count</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>
<p>(a)
What is the return value when</p>
<ul>
<li><code>n</code> is 8 and <code>k</code> is 2?  </li>
<li><code>n</code> is 81 and <code>k</code> is 3?  </li>
<li><code>n</code> is 100 and <code>k</code> is 5?</li>
</ul>
<p>Answer these questions by reading the code first, instead of trying it out on a computer (you can verify later).</p>
<p>(b)
What is the mathematical expression that our mystery function here is trying to compute based on the examples above?</p>
<p>(c)
Give a pair of inputs that would cause the function to return the wrong answer.</p>
<p>(d)
Give a pair of inputs that would cause the function to loop forever.</p>
<div class="footnote">
<hr />
<ol>
<li id="fn:1">
<p>Since a <code>long</code> variable can only store a limited range of values, eventually <code>i</code> will overflow and become positive again and reach the value 2.  So the loop will still terminate, albeit after a long time (no pun intended) if we consider overflow.  For CS1010, we still consider such a loop as an infinite loop.&#160;<a class="footnote-backref" href="#fnref:1" title="Jump back to footnote 1 in the text">&#8617;</a></p>
</li>
</ol>
</div>
                
              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
    <div class="md-footer-nav">
      <nav class="md-footer-nav__inner md-grid" aria-label="Footer">
        
          <a href="10-assert.html" class="md-footer-nav__link md-footer-nav__link--prev" rel="prev">
            <div class="md-footer-nav__button md-icon">
              <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
            </div>
            <div class="md-footer-nav__title">
              <div class="md-ellipsis">
                <span class="md-footer-nav__direction">
                  Previous
                </span>
                10. Assertion
              </div>
            </div>
          </a>
        
        
          <a href="12-invariant.html" class="md-footer-nav__link md-footer-nav__link--next" rel="next">
            <div class="md-footer-nav__title">
              <div class="md-ellipsis">
                <span class="md-footer-nav__direction">
                  Next
                </span>
                12. Loop Invariant
              </div>
            </div>
            <div class="md-footer-nav__button md-icon">
              <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M4 11v2h12l-5.5 5.5 1.42 1.42L19.84 12l-7.92-7.92L10.5 5.5 16 11H4z"/></svg>
            </div>
          </a>
        
      </nav>
    </div>
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
          <div class="md-footer-copyright__highlight">
            Copyright by Department of Computer Science, National University of Singapore 2020
          </div>
        
        Made with
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs
        </a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="assets/javascripts/vendor.77e55a48.min.js"></script>
      <script src="assets/javascripts/bundle.9554a270.min.js"></script><script id="__lang" type="application/json">{"clipboard.copy": "Copy to clipboard", "clipboard.copied": "Copied to clipboard", "search.config.lang": "en", "search.config.pipeline": "trimmer, stopWordFilter", "search.config.separator": "[\\s\\-]+", "search.result.placeholder": "Type to start searching", "search.result.none": "No matching documents", "search.result.one": "1 matching document", "search.result.other": "# matching documents", "search.result.more.one": "1 more on this page", "search.result.more.other": "# more on this page", "search.result.term.missing": "Missing"}</script>
      
      <script>
        app = initialize({
          base: ".",
          features: [],
          search: Object.assign({
            worker: "assets/javascripts/worker/search.4ac00218.min.js"
          }, typeof search !== "undefined" && search)
        })
      </script>
      
        <script src="javascripts/config.js"></script>
      
        <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
      
        <script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js"></script>
      
    
  </body>
</html>