Iterative or Just Recursive?

Here's a list of procedure definitions. Can you figure out if they count as iterative (tail-recursive), or just plain recursive? How about the amount of time they'll take, in big-O notation?

A few of these might be a little too complex for a midterm...but maybe not. It's good to know how to do them, anyway.

```
(define (count sent)
  (if (empty? sent)
      0
      (+ 1 (count (bf sent))) ))
```
(show answer)
Recursive, O(n)

The recursive call is not the last thing we do in the COUNT procedure, so it can't be iterative.

The procedure is O(n), where n is the size of the input sentence, because:
1. There is at most one recursive call per call to COUNT.
2. The recursion only stops when the sentence is empty.
3. The sentence gets one element shorter with each recursive call.
(hide answer)
```
(define (count sent)
  (define (helper sent so-far)
    (if (empty? sent)
        so-far
        (helper (bf sent) (+ 1 so-far)) ))
  (helper sent 0) )
```
(show answer)
Iterative, O(n)

The COUNT procedure just defers to HELPER, so it's only HELPER's behavior that matters. And the recursive call is the last thing we do in HELPER.

COUNT is O(n), where n is the size of the input sentence, because:
1. COUNT calls HELPER once and is done.
2. There is at most one recursive call per call to HELPER.
3. The recursion only stops when the sentence is empty.
4. The sentence gets one element shorter with each recursive call.
(hide answer)
```
(define (how-big x)
  (if (<= x 1)
      1
      (+ 1 (how-big (ceiling (/ x 2)))) ))
```
Somewhat tricky. CEILING rounds numbers up to the nearest integer.

(show answer)
Recursive, O(log(x))

Again, there's more work to do after the recursive call, so this isn't tail-recursive.

The procedure is O(log(x)), because:
1. There is at most one recursive call per call to HOW-BIG.
2. The recursion only stops when x is less than or equal to 1.
3. x effectively gets halved each time, and it takes about log(n) "halvings" to get down to 1.
This was a tricky one! For those who care, it's actually O(ceiling(log(x))), but again, that's basically a constant added to the value which we can ignore.

(hide answer)
```
(define (mystery x y)
  (cond ((<= x 0) y)
        ((= 0 (remainder x 2)) (mystery (- x 3) (+ x y)))
	(else (mystery (- x 1) y)) ))
```
(show answer)

Iterative, O(x)

Yes, this is properly tail-recursive! Even though there are two recursive calls to MYSTERY, they are in different COND clauses. That means that there will only be one recursive call, and it will again be the last thing that happens.

Calculating the order of growth is harder, but again, we know that the recursion ends when x reaches 0. There are two ways to do this:

The More Rigorous Way: x always decreases by either 1 or 3 in each recursive call, but that means it flips from odd to even and back. This means that it's guaranteed to decrease by 4 after two recursive calls. This puts the order of growth at O(2x/4) (doubling x will increase the running time by about x/2 calls), which, after dropping constants, is O(x).

The Easier Way: Ignoring the clauses of the COND, the fastest x can shrink is by 3 each recursion, and the slowest is 1 each recursion. Both of those are O(x) (can you see why?), and we know the rate of growth of MYSTERY is somewhere between these, so it must also be O(x).

(hide answer)
```
; Sorts the numbers in NUMS
(define (selection-sort nums)
  ; Selects the highest number in NUMS that's less than LIMIT
  (define (select-highest nums highest-so-far)
    (cond ((empty? nums) highest-so-far)
	  ((> highest-so-far (first nums))
           (select-highest (bf nums) highest-so-far) )
	  (else (select-highest (bf nums) (first nums))) ))

  ; Uses SELECT-HIGHEST to add the next highest number in UNSORTED to SORTED
  (define (helper unsorted sorted)
    (if (empty? unsorted)
	sorted
	(let ((highest (select-highest (bf unsorted) (first unsorted))))
	  (helper (remove highest unsorted) (se highest sorted)) )))
  (helper nums '()) )
```
A hard one!...with a long answer

(show answer)
Let's break this into two parts, SELECT-HIGHEST and HELPER. The data for SELECTION-SORT is, of course, the same as HELPER's, because all SELECTION-SORT does is call HELPER.

SELECT-HIGHEST: Iterative, O(n)

Like MYSTERY above, we do have two recursive calls to SELECT-HIGHEST, but they're in different COND clauses, and we just return the result, so this still counts as tail-recursive.

The procedure is O(n), where n is the size of the input sentence, because:
1. There is at most one recursive call per call to SELECT-HIGHEST.
2. The recursion only stops when NUMS is empty.
3. NUMS gets one element shorter with each recursive call.
That's SELECT-HIGHEST. How about HELPER?

HELPER: Iterative, O(n²) (that's O(n squared), if your browser doesn't like the "²" character)

You don't have to understand all of this, though if you do you'll know you have a pretty solid grasp on both concepts and how to figure them out. To summarize, HELPER is effectively tail-recursive (yes, even mutual recursion can count). The numbered items at the end of the answer sum up the running time.

There's an interesting twist this time: HELPER doesn't end with a plain recursive call, but rather with a LET-expression. As you know, LET is actually a procedure call, so you'd think this ruins tail-recursion. However, it's also the last thing that HELPER does, so it can still get the same sort of benefits. In addition, the body of the LET simply calls HELPER again, bouncing the recursion right back.

Put casually, because no call to HELPER is ever waiting on another call to HELPER to return (directly or indirectly), HELPER still counts as tail-recursive.

Note that while HELPER itself is tail-recursive, we wouldn't be able to say the entire process is iterative if SELECT-HIGHEST was implemented in a non-iterative way.

As for the order of growth, consider all the procedures called by HELPER. IF is a special form. EMPTY? takes O(1) (constant) time. The LET expression takes however long its arguments take, plus however long the body takes. SELECT-HIGHEST takes O(n) time, as decided by the first half of the question. REMOVE, as it happens, can be implemented iteratively in O(n) time (though it requires some constructs we haven't seen yet). SE takes O(1) time when attaching a word to the beginning of a sentence. And then there's one recursive call to HELPER.

So:
1. There is at most one recursive call per call to HELPER.
2. A single call to HELPER has two O(n) calls.
3. The recursion ends when UNSORTED is empty.
4. UNSORTED gets one element shorter with each recursive call.
So there are N recursive calls to HELPER, each of which has O(n) operations in it. So HELPER (and thus SELECTION-SORT) is O(n²).

(hide answer)
```
(define (two-to-the n)
  (if (= n 0)
      1
      (else (+ (two-to-the (- n 1)) (two-to-the (- n 1)))) ))
```
Worth knowing how to solve.

(show answer)
Recursive, O(2^n) O(2-to-the-nth-power)

(As you've probably figured out, this is a terrible way to compute powers of 2. If we had used multiplication, this would have been a simple recursive problem with O(n) growth.)

Once last time, there's more work to do after the recursive calls, so this isn't tail-recursive. In general, when you see two recursive calls in the same IF or COND clause (or if there are no IFs or CONDs), it's very hard to make the problem completely iterative. Sometimes you can get away with making one call tail-recursive, but the other won't be.

The procedure is O(2^n), because:
1. There are two recursive calls per call to TWO-TO-THE, except in the base case.
2. The recursion only stops when n is 0.
3. n is reduced by 1 with each recursive call.
4. Thus, there are n levels of recursion, and 2-to-the-k calls on the kth level. This comes out to O(2^n).
If there had been three recursive calls, it would have been O(3^n). If n had gone down by two each time, it would have been O(2^(n/2)). You get the idea. (This sort of thing will come up a lot more in CS61B, and CS170 if you take it.)

(hide answer)

Back to Jordy's home page | Course home page