3 ms·

Functional languages will typically guarantee you that tail recursion is constant space. The exception is languages running on a FP adverse runtime such as the

• Twisol 5y ago
  Mutual single recursion is still a loop; you just pick where you want to cut the cyclic dependencies to return to the top. In the worst case, you can put a `switch` in the loop and track what state you're in, although that's gross (you have to keep the union of all variables that might be used in each state). Multiple recursion, like in `fib n = fib (n - 1) + fib (n - 2)`, is more general than loops... in a world without higher-order functions. You can make such a function tail-recursive by doing the continuation-passing transform, which basically just makes the stack explicit. (You'd then want to "defunctionalize the continuation" [0] to clean up.) (I've actually done this in Java! Writing the multiply-recursive solution is sometimes a lot easier to do (and verify); transforming it into an iterative solution mechanically exposes a lot more hidden details, but you still have your recursive solution you can test and compare against.) [0] http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...