1

In a recursive function call it is all about a implicit stack maintenance, so is it possible to replace all the recursive functions with an iterative one using a stack explicitly?

sb15
  • 313
  • 5
  • 18
  • Are you asking if Lisp can be implemented in low-level language? – John Coleman Aug 04 '15 at 08:36
  • @ John Coleman no i'm asking for a generalized way. – sb15 Aug 04 '15 at 14:23
  • the point of my tangential comment was that the answer is *obviously* yes because languages like Lisp are routinely implemented in low-level languages which lack recursion. Recursion is a higher-order abstraction which is in practice almost always implemented in terms of lower level abstractions (such as stacks) which are themselves implemented in terms of even lower level abstractions. – John Coleman Aug 04 '15 at 14:27

1 Answers1

0

Yes. Of course it will be slower then using "real" stack but I can think of two advantages: - code isn't constrained by native stack size - it is easy to break from recursion if it was just used to search for value ( compare with breaking out of a recursion )

Here is a nice example of using explicit stack instead of recursion

Community
  • 1
  • 1
user158037
  • 2,659
  • 1
  • 24
  • 27