In pure functional languages, say writing factorial function as,
fact.0 = 1
fact.n = n*fact.n-1
as this function is stack recursive, could anybody explain difference between stack recursive and tell recursive functions?
Thanks in advance.
Asked
Active
Viewed 716 times
2
-
1Do you mean tail recursive ? – hivert Jul 24 '13 at 07:09
-
2possible duplicate of [What is tail-recursion?](http://stackoverflow.com/questions/33923/what-is-tail-recursion) – hivert Jul 24 '13 at 07:10
-
Yes, but i want difference between tail recursive and stack recursive functions. – Jul 24 '13 at 07:18
-
it will be great if anybody give me factorial function with other tail recursion. – Jul 24 '13 at 07:22
1 Answers
3
The difference between tail recursion and stack recursion (as you call it) is that tail recursive functions can be transformed into imperative code that will not use the call stack (i.e., essentially a while loop), while with stack recursion, the stack depth is proportional to the recursion depth. This could mean that the program overflows the stack.
Note that "transformation into imperative code" is what takes commonly takes place in code generation, as the output language of compilers is often Assembly, C or some other low level imperative language.
Note that this has nothing to do with functional or even pure functional languages, you have the same problem in every language that supports recursion. It is only that in some functional languages, recursion is the only way of looping.
Ingo
- 36,037
- 5
- 53
- 100