Scheme recursion with dotted-tail notation

I am trying to do exercise 2.20 from SICP. It has introduced the dotted-tail notation. Before I can finish the exercise I need help understanding what is wrong with this test program I have written:

(define (f . b)
     (if (null? b) '() (cons (car b) (f . (cdr b)))))

When I enter (f 1 2 3) into the interpreter, instead of getting what I expected which was (1 2 3), I get a "maximum recursion depth exceeded" error.

I cannot see what I have done wrong though. b is the list (1 2 3), so I should get (cons 1 (f . (2 3)) => (cons 1 (cons 2 (f . (3)))) => (cons 1 (cons 2 (cons 3 (f . ())))) => (1 2 3).

I suspect the problem is that the dotted notation only works with define, but I would like to write a recursive function. How do I do this?

Solution

The dotted-tail notation can be used with define, where it means that extra arguments are collected together in a list. With OP (define (f . b) ;...), in a function call like (f 1 2 3), b is bound to the list (1 2 3) in the function body. You can't use dotted-tail notation in function calls, though.

But just removing the dot from the attempted function call (f . (cdr b)) will not work, either. The problem is that (cdr b) is a list, so after the first recursive call you have (f (cdr b)) which means that the value which is passed to f is the list (cdr b), and this list is collected into another list and bound to b in the new function body because of the way the function is defined.

If the initial call were (f 1 2 3), then the arguments would be collected into a list so that b would be bound to (1 2 3) in the first call. Then (car b) would be 1, and the subsequent call would be (f (2 3)). Then the argument (2 3) would be collected into a list so that b would be bound to ((2 3)) in the second call. Now (car b) is (2 3), which is not at all what is desired.

Later in the book apply will be introduced, and that provides a way out of the conundrum:

(define (g . b)
  (if (null? b)
      '()
      (cons (car b) (apply g (cdr b)))))

But, since we do not yet know about apply, we must be creative. Another approach is to define a helper function inside of f that takes a list argument instead of an arbitrary number of arguments:

(define (f . b)
  (define (helper xs)
    (if (null? xs)
        '()
        (cons (car xs) (helper (cdr xs)))))
  (helper b))

Now, the recursive calls are to helper, which is expecting a list argument.

Sample interactions:

> (g 1 2 3)
(1 2 3)
> (f 1 2 3)
(1 2 3)