SUNY Geneseo Department of Computer Science

Recursion, Part 2

Previous Lecture

Questions?

Structure of Recursive Algorithms

Designing Recursive Algorithms

Sections 6.2 and 6.3

Recursive probelm has to get smaller

• Check condition or
• Count an index down
  • Usually to 0 where you can do nothing
  • Maybe to 1 where some simple thing has to be done
• Index needn't be a number, anything that can "decrease" works

Recursive algorithms can call other recursive algorithms

• Mutual recursion

        a1()
            ... a2() ...
        a2()
            ... a1() ...

Possible problems

• Check condition before recursive call
• Counting down usually better than counting up -- easier to recognize stopping condition

Value producing recursions

• All cases must return something

Design a recursive algorithm that counts the number of times a character, c, occurs in a string

    int countOccurrences( char c, String str )
        if str == ""
            return 0
        else if first char of str == c
            return 1 + countOccurrences(c,str.substring(1))
        else
            return 0 + countOccurrences(c,str.substring(1))

• "substring" here is modelled on Java's, so "str.substring(1)" is all characters in "str" except for the first
• Or, a tempting but less reliable approach

    global count
    int countOccurrences( char c, String str )
        if str == ""
            return count
        else if first char of str == c
            count = count + 1
            return countOccurrences(c,str.substring(1))
        else
            return countOccurrences(c,str.substring(1))

Search an array indexed 0 to n for a value x, return true or false

    bool search( array A, int n, x )
        if n < 0
            return false
        else
            return    A[n] == x
                   or search( A, n-1, x )

Search a sorted array (increasing order) A, between positions low and high, for x

• Binary search

    bool binSearch( A, low, high, x )
        if ...
            ... middle ... / 2

• Completing a recursive form of binary search is an exercise for the interested listener (but only if you're interested, it won't be collected or graded in any way)

Next

More advanced recursion

Read Sections 6.4 and 6.5

Next Lecture