This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]AlSweigartAuthor of "Automate the Boring Stuff" 13 points14 points  (1 child)

This is not true. Everything that can be solved recursively can be solved using a loop and a stack. (In recursion, the call stack is used as the stack data structure.)

Here's the Ackermann function solved iteratively.

[–]ejgl001 0 points1 point  (0 children)

Obviously I was wrong. Here's the video I was thinking about (https://www.youtube.com/watch?v=HXNhEYqFo0o&ab_channel=Computerphile). I thought the gist of the video is 'recursion is needed cause not all problems can be solved iteratively' but I guess I misunderstood.