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

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.