CODEWITHSUNDEEP
recursiontail-recursioniteration
raisercostin
raisercostin

Reputation: 9189

tail recursive vs iterative algorithms

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

Upvotes: 12

Views: 6450

Answers (3)

Simon1729
Simon1729

Reputation: 1

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.

Upvotes: 0

Ranjit Kumar
Ranjit Kumar

Reputation: 39

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.

Upvotes: 0

sgud
sgud

Reputation: 442

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.

Further reading here

Upvotes: 11

Related Questions