Killever's blog

Converting recursive to iterative ?
By Killever, 13 years ago, In English
Hi all,
some times i got the idea recursively and make memorization but in this problem the memorization table is very huge so i need to compress the table. and i have no idea about compressing the table with recursion i only can make it if it's iterative.
but i can't convert recursive to iterative
so I want to ask two questions :- 
  1. is there any steps to convert from recursive to iterative ?
  2. is any recursive method can be converted to iterative ?
to understand what i mean this is an example 
converting recursive to iterative then compress table see ahmed.abdrabo 
comments in this link CLICK HERE.

thanks for help.
  • Vote: I like it
  • -2
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
To convert recursive process to iterative, first define function parameters as local variable, for example, x.
To simulate recursive call, push x to stack and set x to the value you want to call with next function. After the task in a function is over, then pop the top of the stack and restore x.

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    thanks tatsuhiro.t for replying but i didn't want to convert internal recursive (computer stack ) to external recursive ( my stack ).
    i want to convert it to iterative like the example i mention above.
    thanks
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
If you know, in which order you should compute all states, it is very easy to create N-loops in such way, you always have needed results computed befoure using them
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    sometimes you can find, that order you created gives you ability to reduce one dimention of dynamic, if it doesn't change the result, good examples of such reducing are: Marshal-Floyd algorithm, knapsack, computing number of increasing sequences of sum S(for example for 6: [1,2,3], [1,5], [2,4], [6]).
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It's easy to answer you on your second question. Yes, any recursioc can be caonverted to iterable becouse computer do that :-D In another words, you can do computer's work: make the stack, which should contain current and previous arguments.

So, it's the answer on your first question too.

Sorry for my terrible English
→ Reply