Tail recursion

[EnCey]

First of all, congrats on getting version 2.0 of your book out! That being said, there's something that's been bugging me a lot in the 1.3 version that's still in 2.0, and that's the section about "head/tail recursion".

I've never heard that term being used to refer to that. I'm not an expert in functional programming, but simply googling for it didn't bring up anything either. What it did bring up is, as expected, the concept of tail recursion.

If I recall correctly you stated that you're not an expert in functional programming either, so forgive my asking whether you may have mixed some things up in that section? Head & tail properties of a list are often used in examples that involve tail recursion, but iterating through a list with them in itself isn't tail recursion.

I know the section says "head/tail recursion" and not "tail recursion" so you may know exactly what you're talking about and simply wanted to explain the way lists are traversed in many functional programming languages. However, in that case, I would like to point out the following:

• tail recursion is an important concept in functional programming and should be mentioned. In my opinion it is a lot more important than the way lists are traversed with head/tail properties. You didn't get out of your way to explain how iterators work in object-oriented languages, so why focus on this one detail of functional languages?
• readers that have no experience with functional programming may end up in an interview where they provide this as an example to the question "tell me what tail recursion is", which would be flat out wrong and leave a bad impression.
• I see no scenario where I, as the interviewer in your example, wouldn't follow up with the task "Now make your solution tail recursive" as the example lends itself perfectly to demonstrate the concept (or, if the solution is already tail recursive - like yours - I'd ask about it instead)

So in any case, I believe tail recursion should be mentioned as a concept, if nothing else to prevent confusion of unaware readers.

[robconery]

Since I'm using Elixir in many examples in that chapter I decided to use the term since the head and tail are passed with the list - you just have to pass the list. With tail recursion you pass the tail and (from what I understand) "splice" the head... Elixir does this for you and you can match against it.

I can see how that would be confusing, especially in an interview setting. Concepts with names are super important and I agree :). I also think that an interviewer (if they were a good one) wouldn't say "dead wrong" if a candidate used the term "head/tail" recursion. I could see them prodding the candidate saying "did you mean". This is an important distinction to make because, to me, that's the difference between a good job and a bad job :).

Either way - I will update the section to reference tail recursion as yes, it needs to be more accurate!

Cheers and thanks!

[robconery]

Ah - I can see now why this would be ultra confusing :) this isn't in the functional programming chapter! Ha - yeah I agree on this completely :) I've just changed it and will push with the next rev.

Cheers

[EnCey]

I believe we're still not talking about the same thing here, so I'll try to explain what I understand under the term "tail recursion". Consider these two C-like functions:

public static int factorial(int mynumber) {
    if (mynumber == 1) return 1;
    return mynumber * factorial(mynumber - 1);
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) return sofar;
    return tail_factorial(mynumber - 1, sofar * mynumber);
}

In the first one, the factorial method must wait for the result of the recursively called factorial so it can multiply it with mynumber.

In the second one, the result of the recursively called tail_factorial is not processed by the calling function, it is returned as-is. Thus the function is "tail recursive", which enables compilers that support this concept to optimize the code: when the tail_factorial method reaches the point where it calls itself, it passes control on to the called method, so to say, and ends.

In the first one, the calling method stays "alive" (its stack frame is kept around) until the called method returns the value. That's more expensive in terms of memory and processing speed. In the second one, the stack frame doesn't have to be kept around and there's no context switch back to the calling method. The linked Wikipedia article from my original post does a much better job at explaining all this than I could.

In my opinion, this concept is important because it's what makes recursive functions comparable to iterative ones in terms of performance. Whether or not its part of the book is of course your decision, but it's very different from what you describe in the book and yet has almost the same name, thus my concerns.

[robconery]

Ah - yes I get it. Thanks (once again) for the clarification - I'll tweak the chapter and yeah I agree it's really important as I do bring up the stack thing in part of the book; I should balance with this as well.

Cheers!