## Friday, 29 July 2011

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