Way to go from recursion to iteration

Question

I ve used recursion quite a lot on my many years of programming to solve simple problems  but I m fully aware that sometimes you need iteration due to memory speed problems   So  sometime in the very far past I went to try and find if there existed any  pattern  or text-book way of transforming a common recursion approach to iteration and found nothing  Or at least nothing that I can remember it would help    Are there general rules  Is there a  pattern

User · Answer

One pattern to look for is a recursion call at the end of the function (so called tail-recursion). This can easily be replaced with a while. For example, the function foo:

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

ends with a call to foo. This can be replaced with:

void foo(Node* node)
{
    while(node != NULL)
    {
        // Do something with node...
        foo(node->left);
        node = node->right;
     }
}

which eliminates the second recursive call.

User · Answer

Generally the technique to avoid stack overflow is for recursive functions is called trampoline technique which is widely adopted by Java devs   However  for C  there is a little helper method here that turns your recursive function to iterative without requiring to change logic or make the code in-comprehensible  C  is such a nice language that amazing stuff is possible with it   It works by wrapping parts of the method by a helper method  For example the following recursive function   int Sum int index  int   array       This is the termination condition  if  int  gt   array Length     This is the returning value when termination condition is true  return 0     This is the recursive call  var sumofrest   Sum index 1  array      This is the work to do with the current item and the    result of recursive call  return array index  sumofrest      Turns into   int Sum int   ar     return RecursionHelper lt int gt  CreateSingular i   gt  i  gt   ar Length  i   gt  0    RecursiveCall  i  rv    gt  i   1    Do  i  rv    gt  ar i    rv    Execute 0

User · Answer

A question that had been closed as a duplicate of this one had a very specific data structure     The node had the following structure   typedef struct       int32 t type      int32 t valueint      double  valuedouble      struct  cNODE  next      struct  cNODE  prev      struct  cNODE  child    cNODE    The recursive deletion function looked like   void cNODE Delete cNODE  c        cNODE next      while  c            next c- gt next          if  c- gt child               cNODE Delete c- gt child                    free c           c next            In general  it is not always possible to avoid a stack for recursive functions that invoke itself more than one time  or even once   However  for this particular structure  it is possible  The idea is to flatten all the nodes into a single list  This is accomplished by putting the current node s child at the end of the top row s list   void cNODE Delete  cNODE  c        cNODE  tmp   last   c      while  c            while  last- gt next                last   last- gt next       find last                      if   tmp   c- gt child                 c- gt child   NULL         append child to last                last- gt next   tmp              tmp- gt prev   last                    tmp   c- gt next               remove current            free c           c   tmp            This technique can be applied to any data linked structure that can be reduce to a DAG with a deterministic topological ordering  The current nodes children are rearranged so that the last child adopts all of the other children  Then the current node can be deleted and traversal can then iterate to the remaining child

User · Answer

The stacks and recursion elimination article captures the idea of externalizing the stack frame on heap  but does not provide a straightforward and repeatable way to convert  Below is one   While converting to iterative code  one must be aware that the recursive call may happen from an arbitrarily deep code block  Its not just the parameters  but also the point to return to the logic that remains to be executed and the state of variables which participate in subsequent conditionals  which matter  Below is a very simple way to convert to iterative code with least changes    Consider this recursive code   struct tnode       tnode int n    data n   left 0   right 0         tnode  left   right      int data      void insertnode recur tnode  node  int num        if node- gt data  lt   num                if node- gt right    NULL              node- gt right   new tnode num           else             insertnode node- gt right  num             else               if node- gt left    NULL              node- gt left   new tnode num           else             insertnode node- gt left  num                 Iterative code      Identify the stack variables that need to be preserved across stack     invocations  that is  across iterations and wrap them in an object struct stackitem         stackitem tnode  t  int n    node t   num n   ra 0         tnode  node  int num      int ra    to point of return     void insertnode iter tnode  node  int num         vector lt stackitem gt  v        pushing a stackitem is equivalent to making a recursive call      v push back stackitem node  num         while v size                      taking a modifiable reference to the stack item makes prepending              si   to auto variables in recursive logic suffice            e g   instead of num  replace with si num          stackitem  amp si   v back             switch si ra                       this jump simulates resuming execution after return from recursive             call              case 1  goto ra1              case 2  goto ra2              default  break                      if si node- gt data  lt   si num                        if si node- gt right    NULL                  si node- gt right   new tnode si num               else                                  replace a recursive call with below statements                     a  save return point                       b  push stack item with new stackitem                       c  continue statement to make loop pick up and start                        processing new stack item                       d  a return point label                     e  optional semi-colon  if resume point is an end                     of a block                   si ra 1                  v push back stackitem si node- gt right  si num                    continue   ra1                                                        else                       if si node- gt left    NULL                  si node- gt left   new tnode si num               else                               si ra 2                                  v push back stackitem si node- gt left  si num                    continue  ra2                                                v pop back              Notice how the structure of the code still remains true to the recursive logic and modifications are minimal  resulting in less number of bugs  For comparison  I have marked the changes with    and --  Most of the new inserted blocks except v push back  are common to any converted iterative logic   void insertnode iter tnode  node  int num                                      vector lt stackitem gt  v      v push back stackitem node  num         while v size                  stackitem  amp si   v back             switch si ra                        case 1  goto ra1              case 2  goto ra2              default  break               ------------------------          if si node- gt data  lt   si num                        if si node- gt right    NULL                  si node- gt right   new tnode si num               else                                                            si ra 1                  v push back stackitem si node- gt right  si num                    continue   ra1                     -------------------------                                  else                       if si node- gt left    NULL                  si node- gt left   new tnode si num               else                                                            si ra 2                                  v push back stackitem si node- gt left  si num                    continue  ra2                 -------------------------                                                               v pop back            -------------------------

User · Answer

Recursion is nothing but the process of calling of one function from the other only this process is done by calling of a function by itself  As we know when one function calls the other function the first function saves its state its variables  and then passes the control to the called function  The called function can be called by using the same name of variables ex fun1 a  can call fun2 a    When we do recursive call nothing new happens  One function calls itself by passing the same type and similar in name variables but obviously the values stored in variables are different only the name remains same  to itself  But before every call the function saves its state and this process of saving continues  The SAVING IS DONE ON A STACK   NOW THE STACK COMES INTO PLAY   So if you write an iterative program and save the state on a stack each time and then pop out the values from stack when needed  you have successfully converted a recursive program into an iterative one   The proof is simple and analytical   In recursion the computer maintains a stack and in iterative version you will have to manually maintain the stack   Think over it  just convert a depth first search on graphs  recursive program into a dfs iterative program   All the best

User · Answer

Another simple and complete example of turning the recursive function into iterative one using the stack    include  lt iostream gt   include  lt stack gt  using namespace std   int GCD int a  int b    return b    0   a   GCD b  a   b      struct Par       int a  b      Par     Par 0  0         Par int  a  int  b    a  a   b  b         int GCDIter int a  int b        stack lt Par gt  rcstack       if  b    0          return a      rcstack push Par b  a   b         Par p      while   rcstack empty                   p   rcstack top            rcstack pop            if  p b    0              continue          rcstack push Par p b  p a   p b               return p a     int main           cout  lt  lt  GCD 24  36   lt  lt  endl      cout  lt  lt  GCDIter 81  36   lt  lt  endl       cin get        return 0

User · Answer

Well  in general  recursion can be mimicked as iteration by simply using a storage variable  Note that recursion and iteration are generally equivalent  one can almost always be converted to the other  A tail-recursive function is very easily converted to an iterative one  Just make the accumulator variable a local one  and iterate instead of recurse  Here s an example in C    C were it not for the use of a default argument       tail-recursive int factorial  int n  int acc   1      if  n    1      return acc    else     return factorial n - 1  acc   n         iterative int factorial  int n      int acc   1    for    n  gt  1  --n      acc    n    return acc      Knowing me  I probably made a mistake in the code  but the idea is there

User · Answer

Just killing time    A recursive function   void foo Node  node        if node    NULL         return         Do something with node        foo node- gt left       foo node- gt right       can be converted to  void foo Node  node        if node    NULL         return          Do something with node         stack push node- gt right       stack push node- gt left        while  stack empty               node1   stack pop             if node1    NULL              continue              Do something with node1             stack push node1- gt right                         stack push node1- gt left

User · Answer

Really  the most common way to do it is to keep your own stack   Here s a recursive quicksort function in C   void quicksort int  array  int left  int right        if left  gt   right          return       int index   partition array  left  right       quicksort array  left  index - 1       quicksort array  index   1  right       Here s how we could make it iterative by keeping our own stack   void quicksort int  array  int left  int right        int stack 1024       int i 0       stack i      left      stack i      right       while  i  gt  0                right   stack --i           left   stack --i            if  left  gt   right               continue           int index   partition array  left  right           stack i      left          stack i      index - 1          stack i      index   1          stack i      right            Obviously  this example doesn t check stack boundaries    and really you could size the stack based on the worst case given left and and right values   But you get the idea

User · Answer

My examples are in Clojure  but should be fairly easy to translate to any language   Given this function that StackOverflows for large values of n    defn factorial  n     if   lt  n 2      1         n  factorial  dec n        we can define a version that uses its own stack in the following manner    defn factorial  n     loop  n n          stack          if   lt  n 2         return 1 stack           else loop with new values        recur  dec n                  push function onto stack               cons  fn  n-1                            n n-1                       stack        where return is defined as    defn return    v stack     reduce  fn  acc f               f acc             v           stack     This works for more complex functions too  for example the ackermann function    defn ackermann  m n     cond      zero  m       inc n        zero  n       recur  dec m  1        else      recur  dec m              ackermann m  dec n        can be transformed into    defn ackermann  m n     loop  m m          n n          stack          cond        zero  m         return  inc n  stack          zero  n         recur  dec m  1 stack          else        recur m               dec n                cons   ackermann  dec m                        stack

User · Answer

Search google for  Continuation passing style   There is a general procedure for converting to a tail recursive style  there is also a general procedure for turning tail recursive functions into loops

User · Answer

It seems nobody has addressed where the recursive function calls itself more than once in the body  and handles returning to a specific point in the recursion  i e  not primitive-recursive   It is said that every recursion can be turned into iteration  so it appears that this should be possible   I just came up with a C  example of how to do this   Suppose you have the following recursive function  which acts like a postorder traversal  and that AbcTreeNode is a 3-ary tree with pointers a  b  c   public static void AbcRecursiveTraversal this AbcTreeNode x  List lt int gt  list            if  x    null                AbcRecursiveTraversal x a  list               AbcRecursiveTraversal x b  list               AbcRecursiveTraversal x c  list               list Add x key    finally visit root               The iterative solution           int  address   null          AbcTreeNode x   null          x   root          address   A          stack Push x           stack Push null               while  stack Count  gt  0                bool  return   x    null               if   return    false                     switch  address                        case A                               stack Push x                           stack Push B                           x   x a                          address   A                          break                      case B                          stack Push x                           stack Push C                           x   x b                          address   A                          break                      case C                          stack Push x                           stack Push null                           x   x c                          address   A                          break                      case null                          list iterative Add x key                            return   true                          break                                                 if   return    true                    address    int  stack Pop                    x    AbcTreeNode stack Pop

User · Answer

Strive to make your recursive call Tail Recursion  recursion where the last statement is the recursive call    Once you have that  converting it to iteration is generally pretty easy

User · Answer

There is a general way of converting recursive traversal to iterator by using a lazy iterator which concatenates multiple iterator suppliers  lambda expression which returns an iterator   See my Converting Recursive Traversal to Iterator

User · Answer

Usually  I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack  In fact  you are replacing the program stack by one of your own  var stack       stack push firstObject       while not empty while  stack length            Pop off end of stack      obj   stack pop            Do stuff         Push other objects on the stack as needed              Note  if you have more than one recursive call inside and you want to preserve the order of the calls  you have to add them in the reverse order to the stack  foo first   foo second    has to be replaced by stack push second   stack push first    Edit  The article Stacks and Recursion Elimination  or Article Backup link  goes into more details on this subject

User · Answer

Even using stack will not convert a recursive algorithm into iterative  Normal recursion is function based recursion and if we use stack then it becomes stack based recursion  But its still recursion   For recursive algorithms  space complexity is O N  and time complexity is O N    For iterative algorithms  space complexity is O 1  and time complexity is O N     But if we use stack things in terms of complexity remains same  I think only tail recursion can be converted into iteration

User · Answer

This link provides some explanation and proposes the idea of keeping  location  to be able to get to the exact place between several recursive calls   However  all these examples describe scenarios in which a recursive call is made a fixed amount of times  Things get trickier when you have something like   function rec          for while loop       var x   rec             make a side effect involving return value x

User · Answer

A rough description of how a system takes any recursive function and executes it using a stack   This intended to show the idea without details  Consider this function that would print out nodes of a graph   function show node  0  if isleaf node   1   print node name 2  else  3   show node left  4   show node  5   show node right    For example graph  A- B A- C show A  would print B  A  C  Function calls mean save the local state and the continuation point so you can come back  and then jump the the function you want to call   For example  suppose show A  begins to run  The function call on line 3  show B  means  - Add item to the stack meaning  you ll need to continue at line 2 with local variable state node A   - Goto line 0 with node B   To execute code  the system runs through the instructions  When a function call is encountered  the system pushes information it needs to come back to where it was  runs the function code  and when the function completes  pops the information about where it needs to go to continue

User · Answer

Thinking of things that actually need a stack   If we consider the pattern of recursion as   if task can be done directly        return result of doing task directly   else       split task into two or more parts     solve for each part  possibly by recursing      return result constructed by combining these solutions     For example  the classic Tower of Hanoi  if the number of discs to move is 1        just move it   else       move n-1 discs to the spare peg     move the remaining disc to the target peg     move n-1 discs from the spare peg to the target peg  using the current peg as a spare     This can be translated into a loop working on an explicit stack  by restating it as   place seed task on stack while stack is not empty     take a task off the stack    if task can be done directly          Do it      else         Split task into two or more parts       Place task to consolidate results on stack       Place each task on stack          For Tower of Hanoi this becomes   stack push new Task size  from  to  spare    while   stack isEmpty          task   stack pop        if task size     1            just move it       else           stack push new Task task size   -1  task spare    task to    task from              stack push new Task 1  task from    task to    task spare              stack push new Task task size   -1  task from    task spare    task to                There is considerable flexibility here as to how you define your stack  You can make your stack a list of Command objects that do sophisticated things  Or you can go the opposite direction and make it a list of simpler types  e g  a  task  might be 4 elements on a stack of int  rather than one element on a stack of Task    All this means is that the memory for the stack is in the heap rather than in the Java execution stack  but this can be useful in that you have more control over it

[recursion] Way to go from recursion to iteration

Examples related to recursion

Examples related to iteration

Examples related to language-agnostic

Examples related to computer-science

Examples related to theory