recursion and tail-recursion differences

[OptimusPrime]

hello,
i need some tuning about this issue,
what is the difference in the structure of the recursions when the final result is computed?
what is the difference in the nature of the “base case” (the case that is handled within the stop condition of the recursion).
maybe some other differences you can think of...
thanks,
OP

[xcallmejudasx]

the final result usually returns a value whereas the other results return another function call. The base case is used to tell the recursive call when to stop calling itself or else you'll end up in a stack overflow and your loop will never end.

[JosAH]

One (theoretical) important aspect is: if the size of a problem is 'n' (n characters in a String, n nodes in a tree etc.) and a recursive solution needs a stack of size O(n) an iterative solution will be better; so e.g. reversing a String or calculating the n-th Fibonacci number is better done iteratively than recursively. On the other hand traversing a (binary) tree just needs O(log(n)) slots on a stack so it can be better done recursively.

kind regards.

Jos