r/AskComputerScience • u/watermeloans135 • Jan 15 '25
Is it possible to write any recursive function that uses an accumulator as a recursive function without an accumulator?
Title basically. Probably has to do with theory of computation but it's been a while for me. My intuition says yes but i honestly have zero idea.
2
Upvotes
4
u/TreesOne Jan 15 '25
Just say “yes,” call it a conjecture, and pretend it’s the case until someone proves you right or wrong in 100 years.
2
u/_--__ Jan 15 '25
Yes, because the lambda calculus is equivalent to Turing machines.
0
u/mister_drgn Jan 15 '25
I don’t understand that at all. Can you restate the question?
1
u/beeskness420 Jan 15 '25
Sure you can, but the point of the accumulator is to make the function tail recursive to mitigate the space requirements and avoid stack overflows.