Recursion to Iteration

Normally, recursion is more readable and easier to understand than iteration. However, recursion can be less efficient than iteration because of the overhead of function calls and the stack. What’s more, some languages don’t optimize tail recursion, which can lead to stack overflow errors.

Luckily, we can always convert recursion to iteration.

Example: Generate balanced parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Such as, with n = 3, a solution set is:
["((()))","(()())","(())()","()(())","()()()"]

Rust

Recursion

fn balanced_parens(n: u16) -> Vec<String> {
    let mut res = Vec::new();
    balanced_parens0(n, n, String::new(), &mut res);
    res
}

fn balanced_parens0(l: u16, r: u16, s: String, res: &mut Vec<String>) {
    if l + r == 0 {
        res.push(s);
        return;
    }
    if l > 0 {
        balanced_parens0(l - 1, r, s.clone() + "(", res);
    }
    if r > l {
        balanced_parens0(l, r - 1, s.clone() + ")", res);
    }
}

Iteration

fn balanced_parens(n: u16) -> Vec<String> {
    let mut res = Vec::new();
    let mut stack = vec![];
    stack.push((n, n, String::new()));
    while let Some((l, r, s)) = stack.pop() {
        if l + r == 0 {
            res.push(s);
            continue;
        }
        if l > 0 {
            stack.push((l - 1, r, s.clone() + "("));
        }
        if r > l {
            stack.push((l, r - 1, s.clone() + ")"));
        }
    }
    res
}

---

Golang

Recursion

func BalancedParens(n int) []string {
	res := []string{}
	balancedParens(n, n, "", &res)
	return res
}

func balancedParens(l, r int, s string, res *[]string) {
	if l == 0 && r == 0 {
		*res = append(*res, s)
		return
	}

	if l > 0 {
		balancedParens(l-1, r, s+"(", res)
	}

	if r > l {
		balancedParens(l, r-1, s+")", res)
	}
}

Iteration

type stackFrame struct {
	l int
	r int
	s string
}

func BalancedParens(n int) []string {
	res := []string{}
	stack := make([]stackFrame, 0, n)
	stack = append(stack, stackFrame{n, n, ""})
	for len(stack) > 0 {
		// pop
		frame := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if frame.l == 0 && frame.r == 0 {
			res = append(res, frame.s)
			continue
		}

		if frame.l > 0 {
			stack = append(stack, stackFrame{frame.l - 1, frame.r, frame.s + "("})
		}

		if frame.r > frame.l {
			stack = append(stack, stackFrame{frame.l, frame.r - 1, frame.s + ")"})
		}
	}
	return res
}

3 Steps to Convert

Let’s dissect what’s going on:

1. Extract the arguments of the recursive function signature into a frame struct(or tuple, etc.)
2. Make a stack and store the first frame with the arguments of the initial call to the recursive function
3. Copy the code inside the recursive function to the iteration loop, and…
   • replace the recursive call with pushing a new frame to the stack
   • replace the return statement with continue to jump to the next iteration

By following these steps, we can 100% convert any recursive function to an iterative one.

Yes, the iterative code still has some space for optimization in some cases, such as reusing variables, etc. But the key point is to show you how to convert recursion to iteration.

Another Example: Flip Tree

In this example, go is a lot easier to convert than rust, because the Ownership system in rust makes things more complicated.

Go

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func flipTreeRecur(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = right, left
	left := flipTree(root.Left)
	right := flipTree(root.Right)
	return root
}

func flipTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		root := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if root.Left != nil {
			stack = append(stack, root.Left)
		}
		if root.Right != nil {
			stack = append(stack, root.Right)
		}
		root.Left, root.Right = root.Right, root.Left
	}
	return root
}

---

Rust

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub fn flip_tree_recur(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    root.as_ref()?;
    let root = root.unwrap();
    let left = root.borrow_mut().left.take();
    let right = root.borrow_mut().right.take();
    root.borrow_mut().left = flip_tree_recur(right);
    root.borrow_mut().right = flip_tree_recur(left);
    Some(root)
}

pub fn flip_tree_iter(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    root.as_ref()?;
    let root = root.unwrap();
    let mut stack = vec![root.clone()];
    while let Some(node) = stack.pop() {
        let mut node = node.borrow_mut();
        let left = node.left.take();
        let right = node.right.take();
        node.left = right;
        node.right = left;
        if let Some(left) = node.left.as_ref() {
            stack.push(left.clone());
        }
        if let Some(right) = node.right.as_ref() {
            stack.push(right.clone());
        }
    }
    Some(root)
}