Review: Arbitrary size data (Lists) and structured data

During last weeks we have covered mechanisms which allow us to store and process arbitrarily large data (the list), and to express structured/templated data objects which consist of several pieces of data (structures, such as an Address).

In using these data mechanisms we have used recursion to consume or build lists one by one. Use uf recursion in this style is named structural recursion, because the program recurses by following the structure/order of elements in the list one by one.

Review example: Find how many times a value appears in a list

In reviewing structural recursion let's solve the problem of finding how many times a value appears in a list. In solving the problem we use structural recursion. We reformulate the problem in recursive style, but do so in a very straightforward manner:

                                 | 0 if list is empty ;THE TERMINATION CONDITION
     Num Occurs(value in list)=  | 1 + Num Occurs(value in rest of list) if value == first of list
                                 | 0 + Num Occurs(value in rest of list) if value =/= first of list

These types of problems are relatively easy because solving the problem for the rest of the list is independent of the first, and a single recursive call is sufficient. In general, during recursion problem whose size is \(n-1\) is independent of problem whose size is \(n\). Same kind of simplicity arises, for example, when finding factorials. We write \(n!=n*(n-1)!\), and finding \((n-1)!\) is an independent problem, and involves a single recursive call.

Once the recursive form is apparent, the program is then written in a straightforward way, e.g. for finding occurrence count of a value in the list:

    (define (numOccurs value list)
            ((empty? list) 0)
            ((= value (first list)) (+ 1 (numOccurs value (rest list))))
            (else (numOccurs value (rest list)))))
    (check-expect (numOccurs 3 empty) 0)
    (check-expect (numOccurs 3 (list 1 2 4)) 0)
    (check-expect (numOccurs 3 (list 1 2 3 4 3)) 2)

Complications 1: Recursive problem is not independent

We run into difficulties with the above solution template when recursive problem's solution is not independent. Consider, for example, the modified problem of "Find the list of positions in the list where a value appears, counting positions from 0". For example:

    (define (occurencePositions value list)
    (check-expect (occurrencePositions 2 (list 2 2 3 2 4 2)) (list 0 1 3 5))
    (check-expect (occurrencePositions 2 (rest (list 2 2 3 2 4 2))) (list 0 2 4))

As you see in the above example the independen solution for the rest of the list has no value since it starts counting positions independently, hence starting from zero again.

Solution with accumulator functions

The general approach to solving these class of problems is using a function which can accumulate the necessary values (the list position in our example):

    (define (occurrencePositions value list firstPosition)
            ((empty? list) empty) 
            ((= value (first list)) 
                    (occurrencePositions value (rest list) (+ firstPosition 1))))
                (occurrencePositions value (rest list) (+ firstPosition 1)))))

    (occurrencePositions 2 (list 2 2 3 2 4 2) 0)

In this case we can recurse into the rest of list, but during this recursion we must remember the index for the first position in the list.

The solution works but has the inconvenience that the users of the solution must remember to add a zero as the last parameter of the function. To avoid such inconveniences, it is customary to provide an additional function which invokes the actual function with proper initial values:

    (define (findOccurrencePositions value list)
        (occurrencePositions value list 0))

Exercise: Split list into two equal size lists

We want to split a list into two lists, which are of equal size. If the list contains an even number of elements, the halves will actually be of the exact same size, but if it has an odd number of elements, one of the halves is allowed to contain one element more than the other half. For example:

    (define (split list)

    (check-expect (split (list 1 2 3 4)) (list (list 1 3) (list (2 4)))
    (check-expect (split (list 1 2 3 4 5)) (list (list 1 3 5) (list (2 4)))


Once again the recursive problems are not independent because one needs to put elements to halves alternatingly and thus must remember which half was used last!

In the solution below we use an accumulator style functon. We start with the original list and two empty lists, At each recursion we add the first element of original list to the first list. Before recursing into the rest of the problem we swap the two lists at each step, to ensure elements are added to these lists alternatingly:

    (define (splitAccumulator half1 half2 originalList)
            ((empty? originalList) (list half1 half2))
            (else (splitAccumulator half2 (cons (first originalList) half1) (rest originalList)))))
    (splitAccumulator empty empty (list 1 2 3 4)) ; returns (list (list 3 1) (list 4 2))
    (splitAccumulator empty empty (list 1 2 3 4 5)) ; returns (list (list 4 2) (list 5 3 1))

(The returned lists are different in their order from the check-expect cases, but this is acceptable as far as their content is valid)

Once again it is helpful to add a convenience function which calls the accumulator style function with default parameters:

    (define (split list)
        (splitAccumulator empty empty list))

NOTE: The function parameter name is originalList instead of list because list is the name of a function which we need to use inside the function we are building. If we use the same name for a parameter, our definition shadows the defined function, making it unusable.

Exercise: Split list into two, with respect to a pivot value

Consider the problem of splitting a list into two lists with respect to a pivot value. The function will take an original list, a pivot value, and return two lists. The first list will contain values in the original list which are less than or equal to the pviot value, and the second list will contain values which are greater than the pivot value. For example:

    (define (splitWithPivot originalList pivot)
    (check-expect (splitWithPivot (list 3 1 2 6 5 7 5) 5) (list (list 3 1 2 5 5) (list 6 7)))
    (check-expect (splitWithPivot (list 3 1 2 6 5 7 5) 8) (list (list 3 1 2 6 5 7 5) empty))


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

    (splitWithPivotAccumulator empty empty (list 3 1 2 6 5 7 5) 5)
    (splitWithPivotAccumulator empty empty (list 3 1 2 6 5 7 5) 8)

    (define (splitWithPivot originalList pivot)
        (splitWithPivotAccumulator empty empty originalList pivot))
    (splitWithPivot (list 3 1 2 6 5 7 5) 5)
    (splitWithPivot (list 3 1 2 6 5 7 5) 8)

Complications 2: Backwards recursion is not efficient

We have run into a problem when computing Fibonacci numbers: \[f(n)=\left\{ \begin{array}{cc} \textrm{undefined} & \textrm{if $n\le 0$ } \\ 1\le n \le 2 & 1 \\ f(n-1)+f(n-2) & \textrm{otherwise} \end{array}\right.\]

When we follow the usual pattern of going backwards, i.e. using problem solution for \(n-1\) in computing the solution for \(n\), the computation becomes very expensive, because each call will start computing from \(n=1\):

        (define (fibonacci n)
            ((not (integer? n)) (error "cannot be computed for non-integers"))
                ((<= n 0) (error "cannot be computed for negative numbers"))
                ((and (>= n 1) (<= n 2)) 1)
                (else (+ (fibonacci (- n 2)) (fibonacci (- n 1))))))
        (check-expect (fibonacci 12) 144)
        (check-expect (fibonacci 35) 9227465)

Note how long it takes for the second example in the above code. In reality, finding Fibonacci numbers is very quick if you start from 1 and go up to \(n\), by remembering the last two Fibonacci numbers at each step.

Reverse recursion example: Factorials

It is possible to do recursion in the reverse way, ie. starting from 0 and going up to n. In the original program we have written for factorial computation the program knew when to terminate: at 0.

    (define (factorial n)
            ((< n 0) (error "invalid"))
            ((= n 0) 1)
            (else (* n (factorial (- n 1))))))

If we want to go the other way, we need to use an accumulator function which remembers where to stop:

    (define (factorialAccumulator n whereNow whatNow)
            ((> whereNow n) (error "invalid state"))
            ((< whereNow n) (factorialAccumulator n (+ whereNow 1) (* whatNow whereNow)))
            (else (* n whatNow))))

    (factorialAccumulator 5 1 1)

    (define (factorial n)
        (factorialAccumulator n 1 1))

Reverse recursion Fibonacci

Now that we have learned the technique of reversing the direction of recursion, we can apply it to Fibonacci numbers problem:

    (define (fibonacciAccumulator n whereNow fn-1 fn-2)
            ((> whereNow n) (error "invalid state"))
            ((< whereNow n) (fibonacciAccumulator n (+ whereNow 1) (+ fn-1 fn-2) fn-1))
            (else (+ fn-1 fn-2))))
    (fibonacciAccumulator 5 3 1 1)
    (fibonacciAccumulator 115 3 1 1)

    (define (fibonacci n)
            ((<= n 0) (error "invalid value"))
            ((<= n 2) 1)
            (else (fibonacciAccumulator n 3 1 1))))
    (fibonacci 200)

Note how fast the function finds the desired value.

Exercise: Compute iterative function logistic map

Consider the -recursive- function definition below: \[\qquad x_{n+1} = r x_n (1-x_n)\] Write a Racket function to compute \(x_n\) for given \(n\), the constant \(r\), and the initial value \(x_0\). For example:

    (define (f n r x0)

Note: This function is called logistic map and gives oscillations of a population whose increase rate is \(r\).


    (define (facc n whereNow r xprev)
        ((> whereNow n) (error "invalid"))
        ((< whereNow n) (facc n (+ whereNow 1) r (* r xprev (- 1 xprev))))
        (else (* r xprev (- 1 xprev)))))

    (define (f n r x0)
       (facc n 1 r x0))