Conditional operation

Example: absolute value

The following function returns the absolute value of the given number

    ; Function: absolute: x:Number -> Number
    ; returns absolute value of given number
    (define (absolute x)
        (cond 
            ((< x 0) (- x))
            (else x)))
    (check-expect (absolute -2) 2)
    (check-expect (absolute 3.1) 3.1)

Logical values and expressions

Logical values can be combined using unary or binary logical operators: and, or and not

    (and true false)
    (or true false)
    (and true (not false))
    (and (< 2 3) (> 2 1))

Example: isBetween

Checking and reporting errors using conditionals

Exercise: bank interest calculation

Consider that a bank uses different interest rates depending on the amount of money you borrow. If the amount is less than \(T\) than the interest rate is \(i_1\), otherwise the interest rate is \(i_2\) (which is smaller). Write a function which takes these parameters, in addition to the amount you borrow, \(A\), and returns how much your total debt will be at the end of one month.

Exercise solution

    (define (debt amount threshold interest1 interest2)
      (cond 
        ((< amount 0) (error "invalid value"))
        ((< amount threshold) (+ amount (* amount (/ interest1 100))))
        (else (+ amount (* amount (/ interest2 100))))))

    (check-expect (debt -1000 5000 10 5) (error "invalid value"))
    (check-expect (debt 1000 5000 10 5) 1100)
    (check-expect (debt 10000 5000 10 5) 10500)

Note that the following version would be incorrect since cond uses only the first condition which holds!

    (define (debt amount threshold interest1 interest2)
      (cond 
        ((< amount threshold) (+ amount (* amount (/ interest1 100))))
        ((< amount 0) (error "invalid value"))
        (else (+ amount (* amount (/ interest2 100))))))

    (check-expect (debt -1000 5000 10 5) (error "invalid value"))
    (check-expect (debt 1000 5000 10 5) 1100)
    (check-expect (debt 10000 5000 10 5) 10500)

Recursion

Recursion is the programming technique which corresponds to mathematical expressions of functions which refer to themselves.

An example is the isBetween function. Remember that the function has to deal with the two cases \(y<z\) and \(y>z\). A rewrite of the function recalls (i.e. recurses onto) itself in one of these cases, by reversing the parameters:

    ; Function: isBetween: x,y,x:Numbers -> boolean
    ; returns whether x is between y and z
    (define (isBetween x y z)
      (cond
        ((<= y z) (and (>= x y) (<= x z)))
        (else (isBetween x z y)))) ;NOTE HOW FUNCTION CALLS ITSELF WITH PARAMETERS REVERSED

    (check-expect (isBetween 2 1 5) true)
    (check-expect (isBetween 1 2 5) false)

Note that the recursion works only if it is guaranteed to stop at some point!

Functional iteration with recursion

An example computation which requires recursing more than once is the factorial function:

\[n! = n\cdot (n-1) \ldots 2 \cdot 1\]

In computing this function one needs to do more than one multiplication, where the number of multiplications depends on the number whose factorial is to be computed.

A recursive, and precise way of writing this function would be \[n!=\left\{ \begin{array}{cc} \textrm{undefined} & \textrm{if $n < 0$ or not an integer} \\ 1 & 0 \le n \le 1 \\ n\cdot (n-1)! & \textrm{otherwise} \end{array}\right.\] This version uses the function as part of itself, so very suitable for recursion, to iterate over the multiplication operations necessary. Many programming languages provide different mechanisms for such iteration. Here we use the functional way of doing it:

        ;Function: factorial: Integer -> Integer
        ; returns factorial of given integer
        (define (factorial n)
            (cond
                ((not (integer? n)) (error "no factorial for non-integers"))
                ((< n 0) (error "no factorial for negative numbers"))
                ((and (>= n 0) (<= n 1)) 1)
                (else (* n (factorial (- n 1)))))) ;FUNCTION CALLS ITSELF

        (check-expect (factorial 1) 1)
        (check-expect (factorial 3) 6)
        (check-expect (factorial 3.14) (error "no factorial for non-integers"))
        (check-expect (factorial -1) (error "no factorial for negative numbers"))

Functional iteration by recursion: termination conditions

When doing iteration by recursion there is the danger on recursion never stopping, hence the name infinite loop. The typical structure in recursion is the function calling itself with a problem whose size is less than the given problem: e.g. factorial(n) calling factorial(n-1). The programmer must check that recursion will stop at some point. For example if we havent't checked for negative numbers case the recursion would continue forever: imagine factorial(-1) calling factorial(-2), and henceforth, going on forever. The stopping condition is named "termination condition"

Exercise: bank interest calculation after many months

Consider the bank interest calculation problem in its simplest form, i.e there's only one interest rate for any amount of debt. This time we want to learn how much money we will owe after \(n\) months, where n is given in addition to the parameters before. Note that debt after a month is calculated by using the amount of debt during the previous month and applyin interest.

Exercise solution

As usual, the essence of the solution lies in formulating the computation in a recursive manner:

\[debt(a,r,n)=\left\{ \begin{array}{cc} \textrm{undefined} & \textrm{if $n < 0$ or not an integer, $a<0$, or $r<0$} \\ a & \textrm{if $n = 0$} \\ debt(a,r,n)*(1+\frac{r}{100}) & \textrm{otherwise} \end{array}\right.\]

The program just follows this formulation:

    ;Function: debt: Number Number Integer -> Number
    ; returns the amount of debt after given many months under given interest rate
    (define (debt amount interestRate months)
      (cond 
        ((or (integer? months) (< amount 0) (< interestRate 0) (< months 0)) (error "invalid input value"))
        ((= months 0) amount)
        (else (* 
               (debt amount interestRate (- months 1))
               (/ (+ 100 interestRate) 100)))))

    (check-expect (debt 1000 10 2) 1210)

Example: Finding Pi

A series expansion of \(\pi\) is as follows \[ \pi = \frac{4}{1} - \frac{4}{3} + \frac{4}{5} - \frac{4}{7} + \frac{4}{9} - \frac{4}{11} + \frac{4}{13} - \cdots \] or \[ \pi = 4\sum_{i=0}^{\infty}\frac{-1^i}{2i+1}\] However we cannot do this infinite computation. But since the components get smaller and smaller we can get an approximation as follows: \[ \pi_n = 4\sum_{i=0}^{n}\frac{-1^i}{2i+1}\] We can rewrite this computation to make it recursive: \[ f(m,n) = \frac{4}{2m+1}-\frac{4}{2m+1}+\cdots+\frac{4}{2n+1} = 4\sum_{i=m}^{n}\frac{-1^{(i-m)}}{2i+1}\] \[ f(m,n) = \left\{ \begin{array}{cc} \textrm{undefined} & \textrm{if $m>n$} \\ 4\frac{1}{2m+1} & \textrm{if $m=n$} \\ 4\frac{1}{2m+1}-f(m+1,n) & \textrm{otherwise} \end{array} \right.\] \[\pi_n=f(0,n)\]

Example: Finding Pi

    (define (findPi m n)
      (cond 
        ((> m n) (error "undefined"))
        ((= m n) (/ 4 (+ (* 2 m) 1)))
        (else (- (/ 4 (+ (* 2 m) 1)) (findPi (+ m 1) n)))))
    (findPi 0 5)
    (findPi 0 50)
    (findPi 0 500)
    (findPi 0 5000)

Which gives the following approximations:

    2.9760461
    3.1611986129870500824735790...
    3.1435886595857872345886366...
    3.1417926135957928384026393...

Exercise: Greatest Common Divisor

We want to find the greatest common divisor (gcd) of two integers, \(k\) and \(l\). Euclid's method to do this is as follows:

Exercise solution

Once again the solution starts with formulating the computation in a recursive manner:

\[gcd(k,l)=\left\{ \begin{array}{cc} gcd(l,k) & \textrm{if $k < l$} \\ l& \textrm{if $l = 1$ or if $k\mod l=0$}\\ gcd(l,k-l)&\textrm{otherwise} \end{array}\right.\]

The program just follows this formulation:

    (define (GCD k l)
      (cond
        ((< k l) (GCD l k))
        ((or (= l 1)(= (modulo k l) 0)) l)
        (else  (GCD l (- k l)))))

    (check-expect (GCD 15 5) 5)
    (check-expect (GCD 144 7) 1)
    (check-expect (GCD 633 18) 3)

Example: Fibonacci numbers

The mathematician Leonardo of Pisa, who is also called Fibonacci, has came up with a formula to find the number of pairs of rabbits in a farm at the end of certain number of months. His assumptions were the following:

With these assumptions, to find number of pairs of rabbits at a given month, one must add to the number during the previous month the number in the month before since they will give birth this month. One arrives at the following formula: \[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.\]

Now we will write a function to compute Fibonacci number for a given integer \(n\).

Example: Fibonacci numbers program

        (define (fibonacci n)
            (cond
            ((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 24) 46368)
        (check-expect (fibonacci 3.14) (error "cannot be computed for non-integers"))
        (check-expect (fibonacci -5) (error "cannot be computed for negative numbers"))

A note on the computation time of Fibonacci

Try computing th Fibonacci number 36. Note how long it takes. Indeed, one can see that the function creates its return value by adding 1s only, since it recurses all the way down to fibonacci(2) or fibonacci(1). Hence computation of fibonacci(n) calls itself twice, the above program can be said to do double recursion. Thus the structure of recursion becomes an important factor which affects its computation time.

A version of fibonacci function which does not have the problem goes from fibonacci(1) and fibonacci(2) upwards, instead of recursing backwards, and thus does not have the problem above. This version is provided here as a food for thought; we will cover this technique in the future.

        (define (fibonacci n)
            (cond
            ((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-alternate n 1 1 3))))

        (define (fibonacci-alternate n fn-1 fn-2 i)
          (cond 
            ((= n i) (+ fn-1 fn-2))
            (else (fibonacci-alternate n fn-2 (+ fn-1 fn-2) (+ i 1)))))
        (check-expect (fibonacci 5) 5)
        (check-expect (fibonacci 12) 144)
        (check-expect (fibonacci 3.14) (error "cannot be computed for non-integers"))
        (check-expect (fibonacci -5) (error "cannot be computed for negative numbers"))
        (fibonacci 36)