tail recursive vs iterative algorithms

Question

I couldn't find articles describing why tail recursive functions should be preferred over iterative algorithms.

I'm not asking why tail recursive is better than simple recursive which I think is clearly explained everywhere.

So why

sum(n) = {
    def sumImpl(n, acc) = if(n <= 0) acc  else sumImpl(n - 1 , n + accumulator)
    sumImpl(n, 0)
}

is preferable to

sum = 0;
while(n>0){ sum += n; n--;}

Old buggy version (and assuming that is not because of such bugs are easier to spot)

sum = 0;
while(n--) sum += n

for its self-evident correctness. and in fact, your second snippet is indeed incorrect - it is equivalent to sum1(n-1), where I write sum1 for your first function which you also named sum. the hand-rolled iteration is so very often much more prone to such errors than its equivalent syntactically recursive formulation. specifically, while(n--) decrements n before it is added to the accumulator, so the very first n value is missed. — Will Ness
– Will Ness, Commented Jul 18, 2022 at 14:41

bbastu · Accepted Answer · 2014-12-14 12:32:37Z

11

Recursion makes a program more readable, but it gives poor performance. Iterative procedures give good performance but are not that readable and may require a local variable to store an intermediate value (mutability). Using tail recursion you will get the best of both worlds and no "sum" variable is needed (immutability). This is very useful in calculating large number sums or factorials, because you will never get a stackoverflow exception as you just forward the result to the next recursive function call.

In a parallel environment immutability is very important. Try to edit your code and pass very large numbers to the function to see the difference.

3 Comments

raisercostin Over a year ago

In the previous case the functional aproach is not more readable. Still should I choose that version?

sgud Over a year ago

Your example is trivial. In this case iterative is obvious choice. To see difference between Iterative, recursive, tail recursive calls try this one. ideone.com/i0md7

raisercostin Over a year ago

So you're saying that the tail recursive one could be more efficient than iterative (6times more for fibonacci)? fibonacciIt - Position: 10000 Time: 137275432 ns fibonacciTail- Position: 10000 Time: 20357861 ns I will check myself :D. Thanks

Ranjit Kumar · Accepted Answer · 2020-06-29 16:43:26Z

0

Recursion consumes more memory (overhead of stack frames) and more cpu cycles (overhead of creating & destroying stack frames). It however makes code more readable. Iterations makes code less readable but frees up more memory and cpu, so it may be needed for constrained environments e.g. IOT decvices, phones etc. See here for a good description https://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Iteration_vs._recursion#:~:text=Iteration%20and%20recursion%20are%20both%20ways%20to%20achieve%20repetition%20in%20programs.&text=All%20iterative%20functions%20can%20be,is%20defined%20as%20tail%20recursion.

answered Jun 29, 2020 at 16:43

Ranjit Kumar

394 bronze badges

1 Comment

raisercostin Over a year ago

While recursion consumes more memory, tail recursion doesn't and can be translated directly to iterative without consuming stack frames. Sometimes iterative is easier to understand than tail recursion and the question is why still prefer tail recursion? It is just a purist approach?

Simon1729 · Accepted Answer · 2022-07-18 13:13:50Z

0

I think the answer lies in your choice of programming paradigm. The declarative style (used in functional programming think Scala) versus imperative style (think iteration in java).

In the functional paradigm we want to avoid side-effects. So we want to deal with expression i.e. code that returns a value. Using recursive functions is one way to do that.

In Java we might change the state of an object inside a loop this would be regarded as a side-effect.

The bottom line, neither approach is necessarily bad. However, we should avoid using imperative constructs such as loops in functional languages use recursion instead.

edited Jul 18, 2022 at 13:13

answered Jul 18, 2022 at 13:10

Simon1729

12 bronze badges

Collectives™ on Stack Overflow

tail recursive vs iterative algorithms

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related