Re: Need help in understanding an example of recursion

[Pascal Bourguignon]

Nikos Apostolakis <nikos.ap@gmail.com> writes:

> Hello group,
>
> I was browsing the source code of SAGE, and I tried to implement in
> elisp the function that computes all the partitions of an integer n.
> So I did the following:
>
> (defun nea-partitions (n)
>   "Return a list with all partitions of the integer n."
>   (if (= n 0)
>       '(nil)
>     (nea-next-partitions (nea-partitions (- n 1)))))
>
> (defun nea-next-partitions (lst)
>   (append (mapcar (lambda (x) (cons 1 x)) lst) 
>         (dolist (elt (reverse lst) value)
>           (when (and elt 
>                      (or (= (length elt) 1) 
>                          (> (car elt) (cadr elt))))
>             (setq value (cons (cons (1+ (car elt)) (cdr elt)) 
>                                           value))))))
>
> But this doesn't work:

Of course.

> (nea-partitions 0) 
>   => (nil)
> (nea-partitions 1) 
>   => ((1))
> (nea-partitions 2) 
>   => ((1 1) (2))
> (nea-partitions 3) 
>   => (1 1 1) (1 2) (3) (2))
> (nea-next-partitions '((1 1) (2))) 
>  => ((1 1 1) (1 2) (3))
> (nea-next-partitions (nea-partitions 2))
>   => ((1 1 1) (1 2) (3) (2))
>
> Is there some subtle[0] point about recursion that I am missing?
> Any help in understanding this will be greatly appreciated.

This is not a question of recursion.  It's a question of something you
should have learned the first day of your first programming course,
that you  should not use global variables and you should initialize
your variables!


Your variable named value is not a local variable of
nea-next-partition.    Moreover, value is a variable that's bound to
new values automatically, read it's documentation. C-h v value RET


To get your own variable named value, you must introduce it with let:

(defun nea-next-partitions (lst)
  (append (mapcar (lambda (x) (cons 1 x)) lst)
          (let ((value '()))
            (dolist (elt (reverse lst) value)
              (when (and elt 
                         (or (= (length elt) 1) 
                             (> (car elt) (cadr elt))))
                (setq value (cons (cons (1+ (car elt)) (cdr elt)) 
                                  value)))))))




Instead of writting (setq v (cons item  v)), you could use push:

(require 'cl) 

(defun nea-next-partitions (list)
  (append (mapcar (lambda (x) (cons 1 x)) list)
          (let ((value '()))
            (dolist (element (reverse list) value)
              (when (and element 
                         (or (= (length element) 1) 
                             (> (car element) (cadr element))))
                (push (cons (1+ (car element)) (cdr element)) value))))))


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.