Can every recursive function be converted into an iterative function?

Yes, any problem that can be solved recursively can also be solved through the use of iteration. In case you don’t know, iteration is the use of a looping construct like a while loop, for loop, etc in order to solve a problem, whereas recursion is the use of a function that calls itself to solve a problem. The reason that iteration can be used to solve any problem that recursion solves is because recursion uses the call stack behind the scenes, but a call stack can also be implemented explicitly (in code) and iteratively (through a for loop, while loop, or any kind of loop). So, whatever recursion gives us behind the scenes can be also be done by implementing a call stack directly in the code itself.

This is true even for problems that seem to be fundamentally recursive. The factorial function which we discussed here can also be implemented iteratively.

Subscribe to our newsletter for more free interview questions.