Блог пользователя Killever

Converting recursive to iterative ?
Автор Killever, 13 лет назад, По-английски
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.
  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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]).
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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
→ Ответить