Trying to solidify tail recursion understanding in Scala

Question

I'm reviewing for an exam in Scala, and trying to figure out this quiz question that I missed. I understand tail recursion as "last call is itself", but I'm confused about the difference between some of these code snippets. Why is this considered tail recursive,

def f(x: Int): Int = {
    if (x % 2 == 0) {1} 
    else {f(x + 1)}

but this, is not?

def f(x: Int): Int = {
    if (x % 2 == 0) {1} 
    else {1 + f(x + 1)}

What exactly does adding 1 to the function do that restricts it from being tail recursive? I'm sorry if this is a silly question, I don't see the affect the number has and want to solidify my understanding. Any other pointers at fully being able to identify tail recursion would be awesome too!

Possible duplicate of [What is tail recursion?](https://stackoverflow.com/questions/33923/what-is-tail-recursion) — Andronicus, Feb 18 '19 at 17:39

score 6 · Accepted Answer · answered Feb 18 '19 at 18:00

Your understanding is not quite right. Tail recursion does not mean "last call is itself" but rather "calling itself is last". That is, a tail-recursive call must be the last action performed by the function. It must be the "tail" of the list of actions that the function performs on that code path. (There must, of course, be a code path that does not include a recursive call).

It is also important to think about how the values in an expression are evaluated rather than the order they appear in the code. This expression

1 + f(x + 1)

is executed in this order:

tmp1 = x + 1
tmp2 = f(tmp1)
res = 1 + tmp2

or alternatively,

add(1, f(add(x, 1))

Written out like this you can see that the call to f is followed by another action, the final +/add. Since the recursive call is not the last action, it is not tail recursion.

Thank you - clarifying the literal really helped me! – Megan Byers Feb 18 '19 at 18:08 — Megan Byers, Feb 18 '19 at 18:08

score 5 · Answer 2 · edited Feb 18 '19 at 21:16

5

In the second snippet, the last call is not "itself", it's +. You have to first get result from f(x+1), and then add 1 to it, before returning. So the current frame has to remain on stack for the f(x+1) call.

Conversely, in the first snippet, there is nothing left to do after f(x+1) is called, because its result becomes the return value. So, the compiler can remove the current frame from stack before making the call, so that the result of f(x+1) invocation will be returned directly to the caller of f(x).

edited Feb 18 '19 at 21:16

Andrey Tyukin

43,673
4
57
93

answered Feb 18 '19 at 17:59

Dima

39,570
6
44
70

Thank you!! I appreciate explaining the stack frames as well – Megan Byers Feb 18 '19 at 18:09
@MeganByers In practice the compiler won't usually "call" `f` at all, it will just jump back to the entry point of `f` using the existing stack frame. This then becomes a simple loop and the compiler can optimise it in the usual way. – Tim Feb 19 '19 at 08:43

score 2 · Answer 3 · answered Feb 19 '19 at 10:46

It often helps to write everything down explicitly in function call notation:

def f(x: Int): Int =
  if (==(%(x, 2), 0) 1 
  else f(+(x, 1))

def f(x: Int): Int =
  if (==(%(x, 2), 0) 1 
  else +(1, f(+(x, 1)))

Can you spot now why in the second example the last call is not to f?

Trying to solidify tail recursion understanding in Scala

3 Answers3