My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure". Anyway I don't understand why, even because I find side-effects useful and difficult to replace a recursive side-effect function with a "pure" one.


Recursion is orthogonal to side effects.

You can have a recursive function with side effects, or without. You can also have a non-recursive function with side effects, or without. It's a matter of opinion and taste whether it's better to avoid side effects in any particular situation. As far as I know, there is no scientific evidence to support a claim that "you should always avoid side effects in any recursive function".

There are reasons to be wary of side effects. They make programs more complex to reason about. This doesn't mean you should never use side effects, but they have tradeoffs. Perhaps one could argue that recursive functions are especially tricky to code and thus one should be especially wary of recursive functions with side effects -- personally, I don't know that I'm particularly persuaded by it. Ultimately, I think it's a matter of taste and judgement, and it's unlikely that any "one-size-fits-all" rule will be scientifically justified.

  • 2
    $\begingroup$ All programs have at least one side effect--warming up the processor. But I hear the GHC folks are hard at work to circumvent thermodynamics to finally have a truly pure programming language. $\endgroup$
    – adrianN
    Jun 6 '16 at 7:38
  • 1
    $\begingroup$ It's worth noting that many of the reasons to use side-effects (performance, simplicity in large projects) wouldn't apply in an Algorithm class, where it's more important to prove your code correct than to actually run it. $\endgroup$
    – jmite
    Jun 6 '16 at 18:50

Your Answer

