Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function )

From: Joe Marshall (jmarshall at alum.mit.edu)
Date: Fri Jan 4 18:10:27 EST 2008

On Jan 3, 2008 9:11 PM, Grant Rettke <grettke at acm.org> wrote:
> This thread had mentioned helping students understand recursion, and
> for some reason, this topic of understanding recursion has come up a
> lot lately "by the water cooler", among other things.
>
> I recently heard that a particular teacher quit trying to teach
> recursion because "it is too hard for students to understand".

Programming is hard.  Let's not bother teaching it.

----
A few years back on comp.lang.lisp someone was working on this problem:

First challenge:
; Call fun for each subsets of 0, 2, ..., n-1 of length k with the following
; constraint: let p be an "ordered" partition of n, eg. (3,2,4,1) |- 10.  If x
; is a chosen number, then it is required that all numbers in the same part of
; the partition smaller than x are chosen, too.


; it may be easier to think of p as a vector where all elements within one
; "part" given by the partition are the same.


; eg: for n=10, k=4, p=(3,2,4,1)==(0,0,0,1,1,2,2,2,2,3)
; (0,1,2,3), (0,1,3,5), (3,5,6,7) are all allowed (there are a lot more...)
; (1,2,3,4), (0,1,4,5) are forbidden


The poster had attempted to write an iterative solution (included below)
that was a true dogs breakfast of arrays, pointer smashing, looping,
modifying index variables, etc.  It didn't work, either.

The recursive solution is 7 lines long (plus an auxiliary function
of 1 line).

Here is the iterative (non-working) version:

(defun strange-combinations (n k l fun vec &optional debug)
  (and debug (print (list 'strange-combinations n k l vec)))
  (let ((level -1))
  (labels ((swap (i j)
                 (and debug (format T "~%swapping ~A and ~A: " i j))
                 (rotatef (aref vec (1- i)) (aref vec (1- j)))
                 (funcall fun))
           (init (n k)
                 (and debug (format T "~%initialise ~A, ~A:  " n k))
                 (fill vec 1 :start 0 :end k)
                 (fill vec 0 :start k :end n))
           (gen (n k l)
                ;      (1 . . . . 1 0 . . 0 | 0 . . . . . . 0)
                ; bzw. (1 . . . . . . . . 1 | 1 . . 1 0 . . 0)
                ;
                ;  ->  (1 . . 1 0 . . . . 0 | 1 . . . . . . 1)
                ; bzw. (0 . . . . . . . . 0 | 1 . . 1 0 . . 0)
                (incf level)
                (and debug (print (list (make-string level) 'gen n k l)))
                (when (and (< 0 k n) (< (car l) n))
                  (let* ((n-rec (- n (car l)))
                         (0-aft (if (< k n-rec) (car l) (- n k)))
                         (1-bef (min k n-rec))
                         (first-0-aft (1+ (max k n-rec))))
                    (dotimes (i (min 0-aft 1-bef))
                      (cond ((evenp i)
                             (gen n-rec (- 1-bef i) (cdr l))
                             (swap (+ first-0-aft i)
                                   (if (plusp (- 1-bef (cadr l) i))
                                   ; (1 . . 1 0 . . 0 | 1 . . . . . . 1 | ...)
                                       (- 1-bef (cadr l) i)
                                   ; (0 . . . . . . 0 | 1 . . 1 0 . . 0 | ...)
                                     (+ (- n-rec (cadr l) i) 1-bef))))
                            (T
                             (neg n-rec (- 1-bef i) (cdr l))
                             (swap (+ first-0-aft i)
                                   ; (1 . . 1 0 . . . . . . . . . . . 0 | ...)
                                   (- 1-bef i)))))
                    (if (evenp (min 0-aft 1-bef))
                        (progn (gen n-rec (max 0 (- k (car l))) (cdr l))
                               (init n-rec (max 0 (- k (car l)))))
                      (neg n-rec (max 0 (- k (car l))) (cdr l)))))
                (decf level))
           (neg (n k l)
                ;      (1 . . 1 0 . . . . 0 | 1 . . . . . . 1)
                ; bzw. (0 . . . . . . . . 0 | 1 . . 1 0 . . 0)


                ;  ->  (1 . . . . 1 0 . . 0 | 0 . . . . . . 0)
                ; bzw. (1 . . . . . . . . 1 | 1 . . 1 0 . . 0)
                (incf level)
                (and debug (print (list (make-string level) 'neg n k l)))
                (when (and (< 0 k n) (< (car l) n))
                  (let* ((n-rec (- n (car l)))
                         (1-aft (min k (car l)))
                         (0-bef (if (< k (car l)) n-rec (- n k)))
                                        ; = n-rec - 1-bef
                         (1-bef (if (< k (car l)) 0 (- k (car l))))
                                        ; = n-rec - 0-bef
                         (last-1-aft (if (< k (car l)) (+ n-rec k) n)))
                    (dotimes (i (min 1-aft 0-bef))
                      (cond ((evenp i)
                             (gen n-rec (+ 1-bef i) (cdr l))
                             (swap (- last-1-aft i)
                                   (if (plusp (- (cadr l) 1-bef i))
                                ; 0 . . . . . . 0 | 1 . . 1 0 . . 0 | 1
                                       (- (+ n-rec 1-bef i 1) (cadr l))
                                ; 1 . . 1 0 . . 0 | 1 . . . . . . 1 | 1
                                     (+ (- 1-bef (cadr l)) i 1))))
                            (T
                             (neg n-rec (+ 1-bef i) (cdr l))
                             (swap (- last-1-aft i)
                                ; (1 . . 1 0 . . . . . . . . . . . 0 | 1
                                   (+ 1-bef i 1)))))
                    (if (evenp (min 1-aft 0-bef))
                        (progn (gen n-rec (min k n-rec) (cdr l))
                               (init n-rec (min k n-rec)))
                      (neg n-rec (min k n-rec) (cdr l)))))
                (decf level)))
    (init n k)
    (funcall fun)
    (gen n k l))))

(defun strange-comb-list (n k l fun &optional debug)
  (let ((vec (make-array n)))
    (strange-combinations n k l
                          #'(lambda ()
                              (and debug (print vec))
                              (let (pos)
                                (dotimes (i n)
                                  (or (zerop (aref vec i))
                                      (push i pos)))
                                (funcall fun pos)))
                          vec debug)))

For what it is worth, I've used this problem as an interview question.
Most applicants fail spectacularly, so I've stopped.


Posted on the users mailing list.