# Thread: recursion and tail-recursion differences

1. Member
Join Date
Dec 2009
Posts
14
Rep Power
0

## recursion and tail-recursion differences

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
Last edited by OptimusPrime; 12-30-2009 at 08:47 AM.

2. 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.

3. 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•