CODEWITHSUNDEEP
recursioniteration
user3243499
user3243499

Reputation: 3151

How to simulate DFS recursive return call using iteration?

I understand the iterative DFS code here. However, it seems to me that when we use iteration, we can only simulate the forward recursive calls of DFS, and not the return statements. For example, if I want to calculate N! using an iteration-simulated version of the recursive solution, we cannot achieve it.

Am I correct with this conclusion? A counter example would be highly appreciated.

Upvotes: 0

Views: 138

Answers (1)

Prune
Prune

Reputation: 77857

I'm not clear where you're confused -- which may be a result of your confusion. The iterative cognate of a return isn't explicit; it's a different process. The control flow is to simply return to the top of the loop. The data flow depends on the algorithm: you pop an item off a stack, or store a result in an array, for example.

If "nth factorial" is the mathematical N! computation, the iterative return is simply the next loop iteration, with the partial product stored in a local variable:

# value of n is given
prod = 1

for i in range(n, 1, -1):
    prod *= i

# yield prod as result

Upvotes: 1

Related Questions