Help understanding Dave Thomas's solution in recursion section of Programming Elixir

Questions / Help
1

https://forums.pragprog.com/forums/322/topics/Exercise:%20ListsAndRecursion-2

I was doing really well until this problem. I can’t wrap my head around the recursion here:

def max([ head | tail ]), do: Kernel.max(head, max(tail))

To me the HEAD in Kernal.max(HEAD ... would always just get overwritten by the head of the tail on each recursion call. I know this is not correct. Can someone walk me through how this is working step by step?

1 Like
2

The easiest way to understand such things is to take a small example list and play it through:

max([1,2,3])
=> K.max(1, max([2,3]))
=> K.max(1, K.max(2, max([3]))
=> K.max(1, K.max(2, 3)
=> K.max(1, 3)
=> 3

As you see, nothing is overwritten.

3 Likes
3

While not technically correct, my mental model for recursion is that every recursive call is spawning an new call to that function while the current call awaits the results.

In this case every call to Kernel.max(head, max(tail)) awaits the result from it’s max(tail).
That max(tail) call is a Kernel.max(head, max(tail)) of it’s own and awaits the result from it’s max(tail) call.

This happens all the way down until max(tail) doesn’t call Kernel.max(head, max(tail)) any more and all these max(tails) calls start returning their results to their respective callers.

1 Like
4

I’m not sure I understand your question.

Your concern is that head would be shadowed on when your function call gets into the next level of recursion, is that it?

Maybe think of it mentally as if on each recursion call you added a different index to the variable. So first you’d have head and tail while in the next call you’d have head1 and tail1, head2 and tail2, etc… Given that it would be obvious that they don’t get overwritten, right? They’re different variables with different names.

Now, this is already the case without the different names! Take into account that each step of the recursion happens on a different context, AFAIK the variables don’t share the scope so there’s no possible overwriting.

I hope that helped a little bit…

1 Like