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

(defun factorial1 (n)
  (let ((st ()) (r 1) (ln n))
    (push ln st)
    (while st
      (cond
       ((>= ln 2)
        (setq ln (- ln 1))
        (push ln 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

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

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
• 'root - before any of the recursive calls; action: print the root; move: none.
• 'left - before the recursive call to the left; action: none; 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 ('root) in the stack.

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

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))))))