General Transformation

• A method to transform any recursive function into an iterative one.
• It requires a stack

  for each of the parameters that might change values in a recursive call,

  for all the local variables (unless they are declared as static),

  for any marks used to store the place in the function where we return after a recursive call was made.

• The stack is inialized to contain the values corresponding to the top level call of the function.
• Introduce a while loop that goes while the stacks are not empty.
• Every recursive call pushes things on the stack and starts a new iteration of the loop.
• The end of a recursive call pops things from the stack.

Transformation

• If more than one recursive call happens, then we need to store a state for each thing we push on the stack.
• This state will mark which of the recursive calls in the sequence we should be doing the next time we see this value.
• If the function returns a value that is computed directly from one of the recursive calls, we can store that in just one variable and compute it as we pop things out of the stack.

One Recursive Call
The stack stores the values of n. The variable r stores the result of the recursive function call.

(defun factorial1 (n)
  (let ((st ()) (r 1))
    (push n st)
    (while st
      (cond
       ((>= n 2)
        (setq n (- n 1))
        (push n st))
       (t (setq r (* r (pop st))))))
    r))

Second Example

f(n) = 2 n2 + 3 f(n-1), 	f(1) = 2

(defun f (n)
  (if (= n 1) 2
    (+ (* 2 n n)
       (* 3 (f (- n 1))))))

Iterative Version
Just like before, the stack stores n, while r is the result of the recursive call. Once we reach the base case and we start coming back up, we need a local variable to store the copy of n as we pop it from the stack, because the test for having reached the base case depends on it.

(defun f (n)
  (let ((st ()) (r 2) (ln 0))
    (push n st)
    (while st
      (cond
       ((> n 2)
        (setq n (- n 1))
        (push n st))
       (t (setq ln (pop st))
          (setq r (+ (* 2 ln ln)
                     (* 3 r))))))
    r))

Labels/States in the General Case

Original Recursive	Iterative
RC(n) // L0 {   ...   RC(n1); // L1   instructions1         RC(n2); // L2   ... }	frame = pop(stack);     n = frame[0]; label=frame[1]; if (label == L1) {   instructions1   push(n, L2);   push(n2, L0); } ...

Tree

• We'll represent a binary tree in Lisp as a list with 3 elements: the root, the left child, and the right child.
• Each of the children is a tree - another list with the same structure.
  

    (23 (51 (18) 
            (33 (5) ))
        (7 () (10)))
  

Tree Structure

(defun root (T) "The root of the tree."
  (if T (car T)))
(defun left-subtree (T) 
  "The left subtree, also a list."
  (if (and T (cdr T))
    (car (cdr T)))) ; (cadr T)
(defun right-subtree (T) 
  "The right subtree, also a list."
  (if (> (length T) 2)
    (car (cdr (cdr T))))) ; (caddr T)

Print in Pre-Order

(defun print-preorder (T)
  "Prints the tree in preorder. Root - L - R"
  (if T
      (progn
        (mapc 'princ (list (root T) " "))
        (print-preorder (left-subtree T))
        (print-preorder (right-subtree T)))))
(setq S '(23 (51 (18) (33 (5))) (7 () (10))))
(print-preorder S)
23 51 18 33 5 7 10 nil

States

• In the general case there is a sequence of two recursive calls. We will use the symbols:
• 'left - before the recursive call to the left; action: print the root; move: to the left child.
• 'right - before the recursive call to the right; action: none; move: to the right child.
• We need a stack to store T. The elements of the stack will be dotted pairs of T and the state.

Iteration

• Remove a pair (T . state) from the stack.
• Based on the state we stored before, we perform the action associated with it.
• Then we store the current T with the state following the current one back in the stack, unless the state is the last one.
• If we need to do a recursive call, we store the new T with the first state ('left) in the stack.

(defun print-preor (T)
  "Prints the list in preorder without recursion."
  (let ((stackT nil) (frame nil) 
        (state nil))
    (push (cons T 'left) stackT)
    (while stackT
      (setq frame (pop stackT))
      (setq T (car frame) state (cdr frame))
      (if T
          (cond ((eq state 'left)
                 (my-print (root T) " ")
                 (push (cons T 'right) stackT)
                 (push (cons (left-subtree T) 
                             'left) stackT))
                ((eq state 'right)
                 (push (cons (right-subtree T) 
                             'left) stackT)))))))

(defun my-print (&rest L)
  (dolist (e L)
    (princ e)))

Optimization

• Since we only have 2 recursive calls, we don't actually need the states.
• We will only store things in the stack while going left.
• When we have to backtrack, we pop T from the stack, move to its right child, then start going left again.
• We need a separate loop that goes all the way left in the beginning.

(defun print-preord (T)
  "An optimization of the function above."
  (let ((stackT ()))
    (while T
      (my-print (root T) " ")
      (push T stackT)
      (setq T (left-subtree T)))
    (while stackT
      (setq T (pop stackT))
      (setq T (right-subtree T))
      (while T
        (my-print (root T) " ")
        (push T stackT)
        (setq T (left-subtree T))))))

Example The combinatorial function.

(defun comb (n m)
      (cond 
       ((= n m) 1)
       ((= m 0) 1)
       ((= m 1) n )
       ((= m (- n 1)) n )
       (t (+ (comb (- n 1) m) (comb (- n 1) (- m 1))))))

We need 3 labels: 'left for the state before the first recursive call, 'right for the state before the second recursive call, and 'done for after the second recursive call. We need a state for that third place in the program because there is an addition operation to do after it.

The variable r will contain the result of the most recently completed recursive call. When we move on to the second recursive call, we store the value returned by the first recursive call in the stack frame as the "result" component. This value can be used when we return from the second recursive call to be added to the variable r to obtain the final result of the function when the state is 'done.

(defun comb2 (n m)
  (let ((st ()) (result 0) (r 0))
    (push (list n m 0 'left) st)
    (while st
      (setq frame (pop st))
      (setq n (car frame) m (car (cdr frame)) 
            result (car (cdr (cdr frame)))
            label (car (cdr (cdr (cdr frame)))))
      (cond 
       ((equal label 'done) (setq r (+ r result)))
       ((= n m) (setq r 1))
       ((= m 0) (setq r 1))
       ((= m 1) (setq r n ))
       ((= m (- n 1)) (setq r n ))
       ((equal label 'left)
        (push (list n m 0 'right) st)
        (push (list (- n 1) m 0 'left) st))
       ((equal label 'right)
        (push (list n m r 'done) st)
        (push (list (- n 1) (- m 1) 0 'left) st))
       (t result)))
    r))