SUNY Geneseo Department of Computer Science

Recursion, Part 2

Previous Lecture

Questions?

6.3.1 Guiseppe Peano's axioms

• a + b = S( a + P(b) )
• What this says
  • S adds 1
  • P subtracts 1
  • a + b = 1 + ( a + b - 1)
• Why?
  • To give a recursive definition of addition
  • To simplify addition to terms of very simple S and P operations
• 2 + 2 example
  • S( 2 + P(2) )
  • = S( 2 + 1 )
  • = S( S( 2 + P(1) ) )
  • = S( S( 2 + 0 ) ) // P(1) = 0
  • = S( S( 2 ) ) // base case
  • = S( 3 ) // S(2) = 3
  • = 4

Recursion

Read Sections 6.2 - 6.4

Recursion going towards smaller problem

Index = part of algorithm (or parameter) responsible for going towards smaller problem.

• Number that goes towards 0 when problem is solved (for example)

Problems:

• Be sure steps are inside conditional
• Upward progression needs current smaller and stopping value

Recursion can also be value-producing

• Shows up a lot in math, e.g., Peano
• Value-producing recursion must return a value

Termination

• Beware of skipping terminating value
• Think in advance about hitting target
• Avoid exact tests (e.g., <= 0 better than = 0)
• Every step has to change test condition
  • or make progress towards stopping condition (amount of progress always bounded away from zero)
• Be careful you really reach stopping condition
• Beware of double conditions - be sure both conditions are valid

        if ( C1 && C2 )
            base case
        else
            recursive case

• Pay attention to logic

Mini-Assignment

Design a recursive algorithm, int powerOf2( int n ), that computes and returns 2ⁿ

    if n >= 0
        for ( n = n; 2 * n; n-- )
            sum = 2*n + sum
        return sum

• But this isn't recursive!

How about

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

or...

    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 )

• Recursive insight:
  • 2ⁿ = 2 * 2^n-1
  • (x^a * x^b = x^a+b)
• Try out This Version in Java

Next

Some more sophisticated uses of recursion

Read Section 6.5

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

Next Lecture