Recursion And Iteration
December 5, 2017
Today’s exercise is about basic programming techniques.
Your task is to pick a function and write two versions of it, one recursive, the other iterative; compare the two versions on readability, programming ease, speed, and any other criteria that are important to you. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python, a Fib implemenation. Seems like iterative is a lot faster, but didn’t really optimize the recursive one that much either.
import cProfile def fib_rec(n): if n == 0: return 0 elif n == 1: return 1 else: return fib_rec(n-1)+fib_rec(n-2) def fib_iterative(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a functions = [fib_rec, fib_iterative] for f in functions: print("Profiling", f.__name__) cProfile.run("for i in range(3): f(29)") # Profiling fib_rec # 4992240 function calls (6 primitive calls) in 7.445 seconds # Ordered by: standard name # ncalls tottime percall cumtime percall filename:lineno(function) # 1 0.000 0.000 7.445 7.445 <string>:1(<module>) # 4992237/3 7.444 0.000 7.444 2.481 fib.py:4(fib_rec) # 1 0.000 0.000 7.445 7.445 {built-in method builtins.exec} # 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} # Profiling fib_iterative # 6 function calls in 0.000 seconds # Ordered by: standard name # ncalls tottime percall cumtime percall filename:lineno(function) # 1 0.000 0.000 0.000 0.000 <string>:1(<module>) # 3 0.000 0.000 0.000 0.000 fib.py:13(fib_iterative) # 1 0.000 0.000 0.000 0.000 {built-in method builtins.exec} # 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} # [Finished in 8.1s]@Rutger: Your algorithms are not the same. The recursive algorithm takes exponential time, the iterative algorithm takes linear time. You might enjoy this program, which is recursive and takes logarithmic time:
(define (fib n) (define (square x) (* x x)) (cond ((zero? n) 0) ((or (= n 1) (= n 2)) 1) ((even? n) (let* ((n2 (quotient n 2)) (n2-1 (- n2 1))) (* (fib n2) (+ (* 2 (fib n2-1)) (fib n2))))) (else (let* ((n2-1 (quotient n 2)) (n2 (+ n2-1 1))) (+ (square (fib n2-1)) (square (fib n2)))))))I am a big fan of recursion but, to give the iterative version a
bit more credit, it can be rewritten as follows, avoiding both
the temporary variable and the mutations.
I suppose someone may object that this version is thinly veiled
recursion but another could counter that tail recursion is
thinly veiled iteration. Perhaps more to the point, both the
following version and the two versions in the solution generate
iterative processes in Scheme (to use SICP terminology if I
recall correctly), although two of them are iterative programs
and one recursive.
(define (gcd-i2 m n) (do ((m (max m n) n) (n (min m n) (modulo m n))) ((zero? n) m) ))Rutger: The first algorithm is actually horribly bad: it’s exponential, because all the smaller Fibonacci numbers are recomputed over and over. If you make it recursive with memoization, it’s linear but can still blow up your stack due to the recursion if n is large.
@chaw: You don’t need min and max. If m < n, the first call swaps them.
I used the temporary variable in the iterative version on purpose, because it is needed in languages that don’t allow simultaneous assignment.
A tail call is just a goto combined with a simultaneous reassignment of local variables. The reassignment part can make code clearer and less error-prone (since we are less likely to forget to modify a variable appropriately) but really both are just different ways of expressing the same underlying computation.
Converting a non-tail recursion into an iterative form can be interesting though. Here’s the naive fibonacci implementation, in Javascript:
Neither recursive call is in tail position, but we can build up the final result in an accumulating parameter, passed between the two calls:
Now one call is in tail position and can fix the other with an explicit continuation function:
To get properly iterative, we can replace the continuation functions with a stack (containing the stored values of n), use an explicit loop and in-place modification everywhere:
function fib(n) { let a = 0, s = [] while (true) { if (n <= 1) { a += n; if (s.length == 0) return a else n = s.pop()-1 } else { s.push(n) n -= 2 } } }As people have observed, this is still a terrible way to compute the fibonacci numbers.
Here’s a solution in Java for serializing an XML tree. The iterative version uses a stack.
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.nio.charset.StandardCharsets; import java.util.Stack; import javax.xml.parsers.DocumentBuilder; import javax.xml.parsers.DocumentBuilderFactory; import javax.xml.parsers.ParserConfigurationException; import org.w3c.dom.Document; import org.w3c.dom.Element; import org.w3c.dom.Node; import org.w3c.dom.NodeList; import org.xml.sax.SAXException; public class Serializer { enum Op { OPEN_ELEMENT, CLOSE_ELEMENT } private static String SerializeIterative(Node node) { StringBuilder sb = new StringBuilder(); Stack<Object> s = new Stack<Object>(); s.push(node); s.push(Op.OPEN_ELEMENT); while (!s.isEmpty()) { Op op = (Op)s.pop(); switch (op) { case OPEN_ELEMENT: { node = (Node)s.pop(); if (node.getNodeType() == Node.TEXT_NODE) { sb.append(node.getTextContent()); } else { Element e = (Element)node; sb.append("<" + ((Element)node).getTagName() + ">"); NodeList children = e.getChildNodes(); s.push(node); s.push(Op.CLOSE_ELEMENT); for (int i = children.getLength()-1; i >= 0; --i) { s.push(children.item(i)); s.push(Op.OPEN_ELEMENT); } } break; } case CLOSE_ELEMENT: { node = (Node)s.pop(); sb.append("</" + ((Element)node).getTagName() + ">"); break; } } } return sb.toString(); } private static String SerializeRecursive(Node node) { short type = node.getNodeType(); if (type == Node.DOCUMENT_NODE) { return SerializeRecursive(((Document)node).getDocumentElement()); } else if (type == Node.ELEMENT_NODE) { Element element = (Element)node; String tag = element.getTagName(); StringBuilder sb = new StringBuilder(); sb.append("<" + tag + ">"); NodeList children = node.getChildNodes(); for (int i = 0; i < children.getLength(); ++i) { sb.append(SerializeRecursive(children.item(i))); } sb.append("</" + tag + ">"); return sb.toString(); } else { // Handle Node.TEXT_NODE, although this also serves as a catch-all. return node.getTextContent(); } } public static void main(String[] args) throws ParserConfigurationException, SAXException, IOException { DocumentBuilderFactory dbFactory = DocumentBuilderFactory.newInstance(); DocumentBuilder dBuilder = dbFactory.newDocumentBuilder(); String html = "<html><body><h1>Hello World</h1><div><p>Test 1</p><p>Test 2</p></div></body></html>"; InputStream is = new ByteArrayInputStream(html.getBytes(StandardCharsets.UTF_8)); Document doc = dBuilder.parse(is); System.out.println("html: " + html); System.out.println("SerializeIterative: " + SerializeIterative(doc.getDocumentElement())); System.out.println("SerializeRecursive: " + SerializeRecursive(doc.getDocumentElement())); } }Output:
It appears there was a problem in the html code i pasted.
Here’s another attempt, this time escaping the angle brackets with backslashes.
Output:
Here’s another attempt, this time adding “sourcecode” markup.
SerializeIterative:
SerializeRecursive: