# 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 Previous message: Problem with recursion? (was [plt-scheme] Re: Novice, needs help writing function ) Next message: [plt-scheme] MrEd: Background color of text-field% with password style Messages sorted by: [date] [thread] [subject] [author]

```On Jan 3, 2008 9:11 PM, Grant Rettke <grettke at acm.org> wrote:
> 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 | ...)
; (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. Previous message: Problem with recursion? (was [plt-scheme] Re: Novice, needs help writing function ) Next message: [plt-scheme] MrEd: Background color of text-field% with password style Messages sorted by: [date] [thread] [subject] [author]