What are the advantages of tail recursive compare to recursive

Question

So tail recursive means a recursive function that uses one recursive call in the body. Moreover it is outermost, meaning that the recursive call is not inside a statement but rather the recursion is done on the parameter of the recursive call. For example(Here I'm using OCaml),

recursive:

let rec fact n =
if n=0 then 1
else n* fact (n-1);;

Tail Recursive:

let fact n =
let rec helper (n,m)=
    if n=0 then m
    else helper(n-1,n*m)
in 
helper(n,1);;

I don't see why would tail recursive be better than the other one?

Also some questions about OCamel: Do we have have to worry about indentations? Because it seem that we don't when i tried it in tryOCamel.

Also, Can we make a new tag for OCaml questions? Please help

Tail recursion doesn't need to do the multiplication on the result each step on the way back but can just return the the original callee. In reality only the first call would be a true function call while the other calls would have been gotos. Recursion which recuire a continuation on the result on the function needs to return to do that step and will often blow the stack if the recursion gets deep enough. Tail recursion doesn't have to grow the stack with a trick called Tail call elimination. — Sylwester, Jan 08 '19 at 02:31
OCaml does not have indentation blocks. Your screenshot shows a syntax error because `;;` terminates the expression but `let rec funct=` is incomplete. Also you seem to have a typo `fuct` instead of `funct` somewhere. Please copy paste your output instead of putting screenshots in because blind people can't read them easily. — lambda.xy.x, Jan 08 '19 at 17:19

score 1 · Accepted Answer · 2019-01-08T02:37:35.620

Tail recursion does not incur the stack depth issues involved with regular recursion. Since tail recursions directly return the result to the parent, the stack frame is discarded when the next recursive call is made. This allows for much deeper(infinite) recursion. Each internal step in the recursive call is essentially replaced with the new call.

In your example:

let rec fact n =
    if n=0 then 1
    else n * fact (n-1);;

The first n in n * fact(n-1) must be stored for each iteration of the call; So it can be used(n * ...) when the stack is unwound.

Your second example passes the n * current result(m) as a parameter, and requires no operations when the stack is "unwound", since the last n * m calculation returns the complete answer.

What are the advantages of tail recursive compare to recursive

1 Answers1