SUNY Geneseo Department of Computer Science

Recursion, Part 3

Previous Lecture

Misc

Hand out Lab 4

Questions?

Using robot class outside of labs - problems with packages

• Many Java compilers want packages = folders
• e.g., geneseo.cs.sc =
  • Folder "geneseo"
    • Folder "cs"
      • Folder "sc"
        • .java files
• Issue for Sun javac, Eclipse
  • Look for term "classpath"

How Recursion Works

Play-act last lecture's power-of-2 algorithm

    int powerOf2( int n )
        if n = 0
            return 1
        if n >= 1
            return 2 * powerOf2( n-1 )
        if n <= -1
            return (1 / 2) * powerOf2( n+1 )

Recursion works like any other message

• Sender sends message
• Waits for receiver to handle it
• Sender resumes after message

Using people to keep track of invocations of methods...

• Mei.powerOf2( 3 )
  • Asks Paul for powerOf2( 2 )
    • Asks Mike for powerOf2( 1 )
      • Asks Greg for powerOf2( 0 )
      • Receives 1
      • Computes 2 * 1 = 2
    • Paul receives 2
    • Computes 2 * 2 = 4
  • Mei receives 4
  • Computes 2 * 4 = 8

Reading Summary

Section 6.5

Review definition of algorithm

• Recursive algorithms really are algorithms, even 'though they don't look like sequence of steps

How recursive algorithm works, like we just did

Inversion - last started is first done

• Examples of inversion

Three parts of recursive algorithm

• General step, always uses recursion
• Final step aka base case
• Test to choose between steps

Multiple recursive references

• Example
• Why multiple recursive references should always be mutrually exclusive -- non-exclusive references can be very slow
• Don't want more than one recursion in a single arm of the algorithm

        a()
            if .....
                "if" arm 1
               ... a() ...
               ... a() ...
            else if ....
                "if" arm 2
                ... a() ...
            else
                "else" arm

Can't have recursive call before test

Hiding recursion / Hiding messy message interfaces

• e.g., squareRoot( n, lowerBound, upperBound )
• Hide this behind

        root( n )
            return squareRoot( n, 0, n ) 

Mini-Assignment

Design a recursive algorithm that makes a robot draw an n-tile line and then go back to its original tile.

Need to retrace steps

Control order of steps by when/where recursive call is

Take as many steps back as you took forward

Algorithm outline

• Go forward n steps
• Turn around (when you reach destination)
• Go back n steps

Alternative

• Move 1 forward and 1 back
• Move 2 forward and 2 back
• ...
• Move n forward and n back

Take advantage of inversion

    if n = 0
        turn around
    else
        paint
        move
        recurse( n - 1 )
        move

• Play-act this too (we started it, we'll finish Friday)

Next Lecture