REVIEW: HOW TO APPLY RECURSION

Case 1: Problem is simple, with single recursion

This class of problems are simple when expressed in recursive form, the function appears only once in recursive definition.

In all of the functions (whether using lists or just math) the function appears only once at the right hand side of its definition recursively. Thus the programs are straightforwards following the definition:

Example: Factorial \[f(n)=\left\{ \begin{array}{ll} \textrm{undefined} & \textrm{if $n<0$}\\ 1 & \textrm{if $0\le n \le 1$}\\ n\cdot {\color{red}{f(n-1)}} & \textrm{if $2\le n$} \end{array} \right.\]

Example: sum of list \[sum(list)=\left\{ \begin{array}{ll} 0 & \textrm{if list is empty}\\ first(list)+{\color{red}{sum(rest(list))}} & \textrm{otherwise} \end{array} \right.\]

Example: How many times a value appears in a list Note that the two appearances below are independent cases. If the function have appeared both in conditions and on the left hand side, we would have worried. Think about how the conditions are checked first then only one of the corresponding values are computed! \[appears(list, value)=\left\{ \begin{array}{ll} 0 & \textrm{if list is empty}\\ 1 + {\color{red}{appears(rest(list), value)}}& \textrm{if $first(list)=value$}\\ {\color{red}{appears(rest(list), value)}}& \textrm{if $first(list)\ne value$} \end{array} \right.\]

Case 2: Double recursion can easily be avoided using helper functions

In the cases below the function appears more than once at the right hand side of its definition. Note that what matters is the function is caled with the same arguments. such cases can be avoided by using a helper function:

Example: logistic map function \[f(n,r)=\left\{ \begin{array}{ll} 0.5 & \textrm{if $n=0$}\\ r{\color{red}{f(n-1,r)}}(1-{\color{red}{f(n-1,r)}}) & \textrm{otherwise} \end{array} \right.\] Then we define a helper function: \[helper(x,r)=rx(1-x)\] an use it to avoid double appearance: \[f(n,r)=\left\{ \begin{array}{ll} 0.5 & \textrm{if $n=0$}\\ helper({\color{red}{f(n-1,r)}},r) & \textrm{otherwise} \end{array} \right.\]

Example: finding max value \[maxf(list)=\left\{ \begin{array}{ll} undefined & \textrm{if list is empty} \\ first(list) & \textrm{if $rest(list)$ is empty} \\ first(list) & \textrm{if $first(list)>{\color{red}{max(rest(list)}}$}\\ {\color{red}{max(rest(list))}}& \textrm{otherwise} \end{array} \right.\] Note that we must check the condition and may have to recompute \(max(rest(list))\). Thus to avoid calling the function with same arguments again we define a helper function: \[maxval(x,y)= =\left\{ \begin{array}{ll} x& \textrm{if $x>y$} \\ y& \textrm{otherwise} \end{array} \right.\] then use it: \[maxf(list)=\left\{ \begin{array}{ll} undefined & \textrm{if list is empty} \\ maxval(first(list),{\color{red}{max(rest(list)}} & \textrm{otherwise} \end{array} \right.\]

Case 3: Double recursion can be avoided by reversing recursion and using accumulator function

This is the case we encounter with computations like Fibonacci, when the function appears on the right hand side twice, with different calling parameters. In the case of Fibonacci, reversing the recursion is necessary:

\[f(n)=\left\{ \begin{array}{cc} \textrm{undefined} & \textrm{if $n\le 0$ } \\ 1\le n \le 2 & 1 \\ {\color{red}{f(n-1)}}+{\color{red}{f(n-2)}} & \textrm{otherwise} \end{array}\right.\]

    ;ACCUMULATOR FUNCTION, REVERSES RECURSION FROM 1 TO n
    (define (fibonacciAccumulator n whereNow fn-1 fn-2)
          (cond
            ((> whereNow n) (error "invalid state"))
            ((< whereNow n) (fibonacciAccumulator n (+ whereNow 1) (+ fn-1 fn-2) fn-1))
            (else (+ fn-1 fn-2))))

    ;CONVENIENCE FUNCTION
    (define (fibonacci n)
        (cond
            ((<= n 0) (error "invalid value"))
            ((<= n 2) 1)
            (else (fibonacciAccumulator n 3 1 1))))

Case 4: Recursive computation is not independent

This is a case where we just have to use accumulator functions, e.g. to find occurrence positions of a value in the list:

    ;ACCUMULATOR
    (define (occurrencePositions value list firstPosition)
        (cond
            ((empty? list) empty) 
            ((= value (first list)) 
                (cons 
                    firstPosition 
                    (occurrencePositions value (rest list) (+ firstPosition 1))))
            (else 
                (occurrencePositions value (rest list) (+ firstPosition 1)))))

    ;CONVENIENCE FUNCTION
    (define (findOccurrencePositions value list)
        (occurrencePositions value list 0))

SOLVING PROBLEMS WITH DIVIDE-AND-CONQUER

When we solved problems we have used recursion to consume the problem one small bite at a time. Divide-and-conquer is a general strategy of dividing the problem into two equal, half-size pieces, solving the halves, and finally combining half-size solutions to provide the full size solution.

We will apply this technique to sorting problems, but we first review some of what we have done about sorting.

Review: sorting with insertion sort

Following is the algorithm we have developed in the past weeks, to implement a basic sorting method called insertion sort:

    ;Function number ascending-sorted-list -> sorted-list
    ;Returns a version of the list where the vlue is inserted in proper order
    (define (insert value sortedList)
        (cond
          ((empty? sortedList) (cons value empty))
          ((< value (first sortedList)) (cons value sortedList))
          (else (cons (first sortedList) (insert value (rest sortedList))))))

    ;Function list ascending-sorted-list -> sorted-list
    ;returns a list obtained by inserting each of the values in the list into sorted list in proper order
    (define (insertAll unsortedList sortedList)
        (cond
          ((empty? unsortedList) sortedList)
          (else 
           (insertAll 
            (rest unsortedList) 
            (insert (first unsortedList) sortedList)))))

    (define (insertionSorter unsortedList)
        (insertAll unsortedList empty))

Measuring performance of insertion sort with long random list

Remember the following function we have written to create a random list of \(n\) integers, each less than \(k\):

    (define (makeRandomList n k)
      (cond
        ((or (< n 0) (< k 0)) (error "invalid input"))
        ((= n 0) empty)
        (else (cons (random k) (makeRandomList (- n 1) k)))))

    (makeRandomList 20 1000)

We can use a random list together with time function in Racket to measure performance of an algorithm. See how the time needed for the following problems differ, with respect to problem size:

    (time (insertionSorter (makeRandomList 1000 2000000)))
    (time (insertionSorter (makeRandomList 2000 2000000)))

Merge sort

Merge-sort is a sorting algorithm which divides the list to be sorted into two equal halves, sorts each half (recursively) and then merges the two sorted lists into one.

We have already implemented the split part of the problem last week:

    ;ACCUMULATOR FUNCTION
    (define (splitAccumulator half1 half2 originalList)
        (cond 
            ((empty? originalList) (list half1 half2))
            (else (splitAccumulator half2 (cons (first originalList) half1) (rest originalList)))))

    ;CONVENIENCE FUNCTION
    ;Function that splits the given list into two equal size halves
    (define (split list)
        (splitAccumulator empty empty list))

In applying merge-sort we use the assumption that an empty list, or a list with one element is already sorted. Therefore the recursive algorithm is as follows:

    (define (merge-sort unsorted)
        (cond
            ((or (empty? unsorted) (empty? (rest unsorted))) unsorted)
            (else (mergeHalvesHelper (sortHalvesHelper (split unsorted))))))
    (check-expect (merge-sort (list 5 2 3 1 7 5)) (list 1 2 3 5 5 7))

The definition needs some helper functions (to avoid unnecessary re-calls):

    ;helper functions
    (define (sortHalvesHelper halves)
        (list (merge-sort (first halves)) (merge-sort (first (rest halves)))))
    (define (merHalvesHelper halves)
        (mergeHalves (first halves) (first (rest halves))))

Now we must define the function to merge the sorted halves:

    (define (mergeHalves half1 half2)
        (cond
            ((empty? half1) half2)
            ((empty? half2) half1)
            ((< (first half1) (first half2)) (cons (first half1) (mergeHalves (rest half1) half2)))
            (else (cons (first half2) (mergeHalves half1 (rest half2))))))

Comparison of insertion sort versus merge-sort performance

Try out!

    (time (insertionSorter (makeRandomList 2000 2000000)))
    (time (merge-sort (makeRandomList 2000 2000000)))

Quick-sort

Quick sort is a very commonly used algorithm for sorting. The idea is as follows: take the first element of a list as pivot, split the list into two partitions, first containing numbers less than or equal to pivot, and the second containing others. Now if you sort these two partitions, put the pviot in their middle, you obtain a sorted list!

To solve the problem we will re-use the partitioning implementation we have done last week:

    (define (splitWithPivotAccumulator lessList greaterList originalList pivot)
      (cond
        ((empty? originalList) (list lessList greaterList))
        ((<= (first originalList) pivot) 
          (splitWithPivotAccumulator (cons (first originalList) lessList) greaterList (rest originalList) pivot))
        (else
          (splitWithPivotAccumulator lessList (cons (first originalList) greaterList) (rest originalList) pivot))))

    ;CONVENIENCE FUNCTÄ°ON
    (define (splitWithPivot originalList pivot)
        (splitWithPivotAccumulator empty empty originalList pivot))

Quick-sort is now easy using this function:

    (define (quick-sort unsorted)
      (cond
        ((or (empty? unsorted) (empty? (rest unsorted))) unsorted)
        (else (combineHelper (first unsorted) (splitWithPivot (rest unsorted) (first unsorted))))))
    (define (combineHelper pivot halves)
        (append (quick-sort (first halves)) (cons pivot (quick-sort (first (rest halves))))))
    (check-expect (quick-sort (list 5 2 3 1 7 5)) (list 1 2 3 5 5 7))

Find median value in a list of numbers

The problem can be solved using quick sort's partitioner.

EXERCISES

  1. Write a program to compute the following function: \[f(n)=\left\{ \begin{array}{ll} undefined & \textrm{if $n\le 0$}\\ 1 & \textrm{if $n=1$}\\ n+f(n-1)& \textrm{otherwise} \end{array} \right.\]
  2. Write a program to compute the following function: \[f(n)=\left\{ \begin{array}{ll} undefined & \textrm{if $n\le 0$}\\ 1 & \textrm{if $n=1$}\\ \frac{n}{f(n-1)}& \textrm{otherwise} \end{array} \right.\]
  3. Write a program to compute the following function: \[f(n)=\left\{ \begin{array}{ll} undefined & \textrm{if $n\le 0$}\\ 1 & \textrm{if $n=1$}\\ n-f(n-1)& \textrm{if $f(n-1)>n$}\\ n+f(n-1)& \textrm{otherwise} \end{array} \right.\]
  4. Write a program to compute the following function: \[f(n)=\left\{ \begin{array}{ll} undefined & \textrm{if $n<0$}\\ 1 & \textrm{if $0\le n \le 1$}\\ \frac{(f(n-1)+f(n-2)}{f(n-1)}& \textrm{otherwise} \end{array} \right.\]
  5. Write a function named filterIntegers that takes a list as an argument which contains mixed type values, and returns a list which contains only the integer values in the given list, for example:

        (filterIntegers (list 3 1.2 "abc" 4 6.4 7)) ;returns (list 3 4 7)

Hint: the function integer? checks if a given value is integer type. 1. Write a function named zip that takes two lists as arguments, and returns a list which blends the two lists by taking one element from each in turns. If one list runs out, it continues with the elements in the other list. For example:

        (comb (list 1 1) (list 2 2 7 3)) ; returns (list 1 2 1 2 7 3)
  1. Write a function named closest which takes a list of numbers, and a value as inputs and finds the number in the list which is closest to the given value. Provide your recursive formulation of the problem.
  2. Consider the following definiton of a Person as data structure:

        (define-struct Person (name age gender))
        (list 
            (make-Person "ali" 18 "male")
            (make-Person "ayse" 19 "female"))

Write a function which takes a list of Person values, and a number as age limit, and returns the people in the list whose age is greater than or equal to the given age.