Need help in understanding an example of recursion

Need help in understanding an example of recursion

[Nikos Apostolakis]

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:

(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.

TIA,
Nikos 


[0] for my level of understanding at least.

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.

Re: Need help in understanding an example of recursion

[Nikos Apostolakis]

Pascal Bourguignon <pjb@informatimago.com> writes:

> Nikos Apostolakis <nikos.ap@gmail.com> writes:
>> 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
>


This is embarasing.  I actually  red the documentation,  and I
thought that in the dolist construction the third argument is
automatically local.  Not sure where I got the impression since 
the example in the manual does initialize the variable!

Thanks for the answer and the tips,
Nikos