Tail Recursion in java

Question

Is this a good example to show tail recursion?

public printName(){
    System.out.println("Smith");
    printName();
}

I'm not intending to do this in real life, but i put this as an example for my exam. Is this one correct?

Yes, except that this will result in infinite recursion (and crash the program when stack space runs out). — nhahtdh, Jul 21 '12 at 13:57
@dasblinkenlight sometimes i come back to view your comment. it never fails to cheer me up. — kritzikratzi, Feb 04 '14 at 20:42

score 20 · Answer 1 · answered Jul 21 '12 at 13:57

20

No, for two reasons:

tail recursion is only valuable when compiler supports it (tail call optimization). In Java it will still end with StackOverflowError
it would be nice to show some stop condition. Your code is equivalent to loop running forever.

Consider almost identical code in Scala, the only difference is that Scala compiler will perform tail call optimization and the loop runs forever:

def printName() {
  println("Smith"); 
  printName()
}

answered Jul 21 '12 at 13:57

Tomasz Nurkiewicz

334,321
69
703
674

4

I don't know: tail recursion is just tail recursion. The compiler can optimize it, but it is besides the point. Correct me if I'm wrong. – nhahtdh Jul 21 '12 at 13:59
1

@nhahtdh: the OP is not asking whether this is tail recursion or not (no doubt in that). He is asking whether this is a **good example** of tail recursion. IMHO it's not. – Tomasz Nurkiewicz Jul 21 '12 at 14:02
2

According to [Wikipedia](http://en.wikipedia.org/wiki/Tail_call) and my own CS memories it does not matter whether or not the language handles tail recursion specially - the example is tail-recursive. – A.H. Jul 21 '12 at 14:03
@A.H.: the fact that the last statement is a recursive call doesn't make tail recursion so important (for the same reason we are not teaching about *head recursion*) - it's the fact that it can be optimized to simple loop. Showing an example of tail recursion on a language that does not support it is misleading - it won't buy you anything in Java. So it's *not* a good example without extra remark ("*note that in Java...*") - so why not show it in pseudo-code or in a language where tail-recursion is actually meaningful? Otherwise you'll see Java developers *thinking* they gained something – Tomasz Nurkiewicz Jul 21 '12 at 14:33

score 15 · Answer 2 · answered Jul 21 '12 at 14:09

A better example of tail recursion would be something like this:

public printName(int level){
    if( level <= 0 )
         return;
    System.out.prntln("Smith");
    printName(--level);
}

This examples includes the important part where the recursion is terminated.

Besides of this: As other answers already noted: Since Java does not optimize tail-recursion, there is no point in using it in this language. So you basically end up to optimize your algorithm yourself - by making it iterative. That's the point of tail-recursion: It can be proved, that any tail-recursive algorithm can be transformed into an iterative algorithm.

score 1 · Answer 3 · answered Jul 21 '12 at 13:58

1

I would say this is an example of tail recursion, as you recurse in the tail of the program :) I do however not think that the JVM will optimize this, which is probably what you want.

answered Jul 21 '12 at 13:58

Jonatan

2,734
2
22
33

Tail Recursion in java

3 Answers3

Linked