-2

I've recently learned about tail-recursions as a way to make a recursion that doesn't crash when you give it too big of a number to work with. I realised that I could easily rewrite a tail-recursion as a while loop and have it do basically exactly the same thing, which lead me wondering - is there any use for recursions when you can do everything with a normal loop?

Yes, recursion code looks smaller and is easier to understand, but it also has a chance of completely crashing, while a simple loop cannot crash doing the same task.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
umnikos
  • 239
  • 1
  • 9
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [on topic](http://stackoverflow.com/help/on-topic) and [how to ask](http://stackoverflow.com/help/how-to-ask) apply here. This question already has many answers on Stack Overflow and the Internet in general. – Prune May 24 '17 at 20:46
  • 2
    Is there any use for loops? Recursion can do everything a loop can. A simple loop can crash by an index out of bounds or integer overflow, but you know, the programmer shouldn't be responsible for making sure their code doesn't crash! – MrZander May 24 '17 at 20:49
  • @Prune I didn't find any of them helpful – umnikos May 24 '17 at 23:18
  • @MrZander recursion also has those two problems :P Tho I guess there are more than one ways to do exactly the same thing... – umnikos May 24 '17 at 23:20
  • Maybe this question shall go to meta so – developer_hatch May 25 '17 at 01:53
  • Possible duplicate of [Recursion or Iteration?](https://stackoverflow.com/questions/72209/recursion-or-iteration) – Román García May 25 '17 at 15:15

2 Answers2

0

I'll take for example the Haskell language, it is Purely functional:

Every function in Haskell is a function in the mathematical sense (i.e., "pure"). Even side-effecting IO operations are but a description of what to do, produced by pure code. There are no statements or instructions, only expressions which cannot mutate variables (local or global) nor access state like time or random numbers.

So, in haskell a recursive function is tail recursive if the final result of the recursive call is the final result of the function itself. If the result of the recursive call must be further processed (say, by adding 1 to it, or consing another element onto the beginning of it), it is not tail recursive. (see here)

On the other hand, in many programming languages, calling a function uses stack space, so a function that is tail recursive can build up a large stack of calls to itself, which wastes memory. Since in a tail call, the containing function is about to return, its environment can actually be discarded and the recursive call can be entered without creating a new stack frame. This trick is called tail call elimination or tail call optimisation and allows tail-recursive functions to recur indefinitely.

developer_hatch
  • 15,898
  • 3
  • 42
  • 75
  • No new information on the problem. I'm currently learning lisp and it has both standard loops and tail-recursion optimisations. I'm trying to find a reason to use tail-recursion when a normal loop does exactly the same job without declaring a function. – umnikos May 24 '17 at 20:33
  • 1
    Have you tried to solve towers of hanoi using loops? – Román García May 24 '17 at 21:44
  • That's a fantastic example @Nykros, in a lot of ways is much more simple to read and understand tail recursion, and sometimes is faster too – developer_hatch May 24 '17 at 21:46
  • 1
    It's for the pair pressure perhaps... Not everybody see geniuses ideas as it is @umnikos – developer_hatch May 25 '17 at 00:17
  • in Common Lisp there is *no* [tail-call-optimization](https://en.wikipedia.org/wiki/Tail_call) guarantee and the use of recursion is frowned upon; [loops](http://www.lispworks.com/documentation/lw51/CLHS/Body/m_loop.htm) are preferred where possible. re Towers of Hanoi, if it's hard to do with loops, it's equally hard to do with *tail* recursion. – Will Ness May 25 '17 at 06:30
0

It's been a long while since I posted this question and my opinion on the topic has changed. Here's why:

I learned Haskell, and it's a language that fixes everything bad about recursion - recursive definitions and algorithms are turned into normal looping algorithms and most of the time you don't even use recursion directly and instead use map, fold, filter, or a combination of those. And with everything bad removed, the good sides of functional programming start to shine through - everything is closer to its mathematical definition, not obscured by clunky loops and variables.

To someone else who is struggling to understand why recursion is great, go learn Haskell. It has a lot of other very interesting features like being lazy (values are evaluated only when they're requested), static (variables can never be modified), pure (functions cannot do anything other than take input and return output, so no printing to the console), strongly typed with a very expressive type system, filled with mind-blowing abstractions like Functor, Monad, State, and much more. I can almost say it's life-changing.

umnikos
  • 239
  • 1
  • 9