help-gnu-emacs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Need help in understanding an example of recursion


From: Pascal Bourguignon
Subject: Re: Need help in understanding an example of recursion
Date: Sat, 02 Jun 2007 22:02:41 +0200
User-agent: Gnus/5.1008 (Gnus v5.10.8) Emacs/22.0.99 (gnu/linux)

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]