Simple Simple Recursion

The next question asks what the following function will return:

((fn foo [x] (when (> x 0) (conj (foo (dec x)) x))) 5)

I hadn't spotted until now that an anonymous function definition can give the function a name, that is to say a name that is visible inside the definition, so you can easily write recursive lambdas.

Anyway clearly this is going to loop down from 5 to 1, building up a list as it goes - so the answer is

(1 2 3 4 5)

Wrong.  This is what happens:

user=> ((fn foo [x] (when (> x 0) (conj (foo (dec x)) x))) 5)
(5 4 3 2 1)

Ha. Maybe it would be clearer (to me at any rate) if I did this with cons instead of conj:

user=> ((fn foo [x] (when (> x 0) (cons x (foo (dec x))))) 5)
(5 4 3 2 1)

The alternative way with cons instead of conj: the x and the call to foo go round the other way. But for lists, conj and cons do the same thing - they add the new element to the start of the list:

user=> (cons 1 '(2))
(1 2)
user=> (conj '(2) 1)
(1 2)

It's with vectors that conj goes the other way:

user=> (conj [2] 1)
[2 1]

when is like if except there is no else part - when the test returns false the when clause returns nil.
You can conveniently cons onto nil to start a list as you would cons onto the empty list:

user=> (cons :a nil)
(:a)
user=> (cons :a '())
(:a)
user=> (cons :a ())
(:a)

Even though nil and () are not the same.

OK, so in this function what happens is the recursive calls burrow their way down from 5 to zero, get a nil when they are down there, and then pop their way back out consing the numbers 1, 2, 3, 4, 5 onto the return list as they go -

(foo 5)
(cons 5 (foo 4))
(cons 5 (cons 4 (foo 3)))
(cons 5 (cons 4 (cons 3 (foo 2))))
(cons 5 (cons 4 (cons 3 (cons 2 (foo 1)))))
(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 (foo 0))))))
(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 nil)))))
(cons 5 (cons 4 (cons 3 (cons 2 '(1))))
(cons 5 (cons 4 (cons 3 '(2 1)))
(cons 5 (cons 4 '(3 2 1)))
(cons 5 '(4 3 2 1))
'(5 4 3 2 1)

Right.  Got it.