SUNY Geneseo Department of Computer Science

Recursion Review

Return to List of Lectures

Misc

Problem set 3 (logic) and lab 2 (experimentation) due tomorrow

• Problem set is graded face to face
• Lab is a report, not face-to-face

Questions?

Problem set problem 3

• Equality via "less", which might look like a < b iff a < b - tolerance
  • vs "a = b" iff b - tolerance < a < b + tolerance
• Is your implementation of "=" via "less" logically equivalent to second "=" above?
• "=" built from "less" is likely be boolean combination of "lesses"
• b - tolerance < a < b + tolerance is really b - tolerance < a and a < b + tolerance
• Use truth tables
• Or boolean algebra
• A little bit of ordinary algebra might help too

Recursion

Section 6.1

• Redefining recursion via analogy of taking a step on a trip
• Analogy of songs
• Degenerate steps
• Definition: recursion is the process of defining something in terms of (smaller versions of) itself

Examples

• Check if an integer is an integer power of 2
  • Observations
    • No integer less than 1 is an integer power of 2
    • 1 is an integer power of 2
    • No other odd number is a power of 2
    • Even n > 1 is an integer power of 2 iff n/2 is
  • "Recursive insight"
  • Algorithm

        boolean powerOfTwo( n )
            if n == 1
                return true
            else if n < 1 or n mod 2 != 0
                return false
            else
                return powerOfTwo( n/2 )

• Could also be written iteratively
  • Tail recursion
    • All recursion(s) are last thing method does
• Print the integers from n down to 1 or 0 decrementing by 2 (i.e., n, n-2, n-4, etc), then print the skipped integers in increasing order (i.e., ..., n-5, n-3, n-1)
  • Insight: print n, print down from n-2 and back, print n-1
  • (Note: insight is missing a check for the base case)
    • Recursive case(s)
    • Base case(s) - no recursion
    • Test(s)
  • Algorithm:

        print( n )
            if n > 1
                output n
                print( n-2 )
                output n-1
            else
                output n

Hand out lab 3

Next

Reasoning about recursion

Read section 7.1.1