Tail Recursion and Side effect

Question

I am actually learning scala and I have a question about tail-recursion. Here is an example of factorial with tail recursion in scala :

 def factorial(n: Int): Int = { @tailrec def loop(acc: Int, n: Int): Int = { if (n == 0) acc else loop(n * acc, n - 1) } loop(1, n) }

My question is updating the parameter, acc as we do it in the function loop can be considered as a side effect? Since in FP, we want to prevent or diminish the risk of side effect.

Maybe I get this wrong, but can someone explain to me this concept.

Thanks for your help

No it doesn't. Pure functions doesn't contain side effects by definition and loop is pure (it depends only on parameters passed in). — om-nom-nom
– om-nom-nom, Commented Oct 11, 2012 at 12:32
I believe that @tailrec should be moved to your loop function. Function loop is recursive, while factorial is not - it never calls itself, it only calls loop. — Petr
– Petr, Commented Oct 11, 2012 at 12:44

Péter Török · Accepted Answer · 2012-10-11 12:37:49Z

7

You aren't actually changing the value of any parameter here (as they are vals by definition, you couldn't, even if you wanted to).

You are returning a new value, calculated from the arguments passed in (and only those). Which, as @om-nom-nom pointed out in his comment, is the definition of pure function.

edited Oct 11, 2012 at 12:37

answered Oct 11, 2012 at 12:32

Péter Török

117k31 gold badges277 silver badges332 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dave Griffith Over a year ago

That said, it's worth noting that it's not unusual for purely functional programs to use this sort of tail-recursive passing to emulate state. Erlang in particular is known for eternally-runing processes that continually pass their state tail recursively to themselves, forever

Ben Over a year ago

It's not so much emulating state as saying explicitly what the concept of state means implicitly. If a (pure) function depends on computations that have already executed, those computations must have resulted in some values which are passed into the function through its arguments.

Collectives™ on Stack Overflow

Tail Recursion and Side effect

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related