Collatz function in scheme

Question

So i'm trying to solve the collatz function iteratively in scheme but my test cases keep showing up as

(define (collatz n)   
    (define (collatz-iter n counter)
            (if (<=  n 1)
                1
            (if (even? n)  (collatz-iter (/ n 2) (+ counter 1))
                           (collatz-iter (+ (* n 3) 1) (+ counter 1)) 
            )
            )
    )
)

However, my test cases keep resulting in "#[constant 13 #x2]". What did I write wrong, if anything?

Answer 1

You forgot to call collatz-iter. Also, it's not clear what do you intend to do with counter, you just increment it, but never actually use its value - your procedure will always return 1 (assuming that the Collatz conjecture is true, which seems quite possible).

I'm guessing you intended to return the counter, so here's how to fix your procedure:

(define (collatz n)
  (define (collatz-iter n counter)
    (if (<= n 1)
        counter ; return the counter
        (if (even? n)
            (collatz-iter (/ n 2) (+ counter 1))
            (collatz-iter (+ (* n 3) 1) (+ counter 1)))))
  (collatz-iter n 1)) ; call collatz-iter

And this is how it works for the examples in wikipedia:

(collatz 6)
=> 9

(collatz 11)
=> 15

(collatz 27)
=> 112

So basically we're counting the length of the Collatz sequence for a given number.

Answer 2

When I try to run your code in Racket I get the error:

no expression after a sequence of internal definitions

This is telling us that the collatz function conatains the collatz-iter definition, but no expression to call it (other than the recursive calls in collatz-iter). That can be fixed by adding a call to (collatz-iter n 0) as the last line in collatz.

However, when you run the program it always returns 1. Not very interesting. If instead you change it to return the value of counter you can see how many steps it took for the sequence to reach 1.

(define (collatz n)   
    (define (collatz-iter n counter)
            (if (<=  n 1)
                counter
            (if (even? n)  (collatz-iter (/ n 2) (+ counter 1))
                           (collatz-iter (+ (* n 3) 1) (+ counter 1)) 
            )
            )
    )
  (collatz-iter n 0)
)

We can check it against a few examples given on the Wikipedia Collatz conjecture article.

> (collatz 6)
8
> (collatz 11)
14
> (collatz 27)
111
> 

Answer 3

You should indent your code properly. With proper formatting, it's

(define (collatz n)   
  (define (collatz-iter n counter)
    (if (<=  n 1)
        1
        (if (even? n)
            (collatz-iter (/ n 2) (+ counter 1))
            (collatz-iter (+ (* n 3) 1) (+ counter 1))))))

which clearly has no body forms to execute, just an internal definition. You need to add a call to collatz-iter, like this:

(define (collatz n)   
  (define (collatz-iter n counter)
    (if (<=  n 1)
        1
        (if (even? n)
            (collatz-iter (/ n 2) (+ counter 1))
            (collatz-iter (+ (* n 3) 1) (+ counter 1)))))
  (collatz-iter n 1))

(I'm not sure what your initial counter value should be. I'm assuming 1 is reasonable, but perhaps it should be zero?) Better yet, since the body it just a call to collatz-iter, you can make this a named let, which is more like your original code:

(define (collatz n)
  (let iter ((n n) (counter 1))
    (if (<=  n 1)
        1
        (if (even? n)
            (iter (/ n 2) (+ counter 1))
            (iter (+ (* n 3) 1) (+ counter 1))))))

It's sort of like combining the internal definition with the single call to the local function. Once you've done this, though, you'll see that it always returns 1, when it eventually gets to the base case (assuming the Collatz conjecture is true, of course). Fixing this, you'll end up with:

(define (collatz n)
  (let iter ((n n) (counter 1))
    (if (<=  n 1)
        counter
        (if (even? n)
            (iter (/ n 2) (+ counter 1))
            (iter (+ (* n 3) 1) (+ counter 1))))))