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.

Advertisements

Pages: 1 2

9 Responses to “Recursion And Iteration”

  1. Rutger said

    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]
    
  2. programmingpraxis said

    @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)))))))
  3. chaw said

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

  4. John Cowan said

    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.

  5. programmingpraxis said

    @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.

  6. matthew said

    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:

    fib = (n) => n <= 1 ? n : fib(n-1) + fib(n-2)
    

    Neither recursive call is in tail position, but we can build up the final result in an accumulating parameter, passed between the two calls:

    fib = (n,a) => n <= 1 ? n + a : fib(n-1,fib(n-2,a))
    

    Now one call is in tail position and can fix the other with an explicit continuation function:

    fib = (n,a,k) => n <= 1 ? k(n+a): fib(n-2,a,t => fib(n-1,t,k))
    

    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.

  7. Daniel said

    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:

    html:               Hello WorldTest 1
    
    Test 2
    SerializeIterative: Hello WorldTest 1
    
    Test 2
    SerializeRecursive: Hello WorldTest 1
    
    Test 2
    
  8. Daniel said

    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:

    html:               \\\Hello World\\\Test 1\\Test 2\\\\
    SerializeIterative: \\\Hello World\\\Test 1\\Test 2\\\\
    SerializeRecursive: \\\Hello World\\\Test 1\\Test 2\\\\
    
  9. Daniel said

    Here’s another attempt, this time adding “sourcecode” markup.

    html:               
    <html><body><h1>Hello World</h1><div><p>Test 1</p><p>Test 2</p></div></body></html>

    SerializeIterative:

    <html><body><h1>Hello World</h1><div><p>Test 1</p><p>Test 2</p></div></body></html>

    SerializeRecursive:

    <html><body><h1>Hello World</h1><div><p>Test 1</p><p>Test 2</p></div></body></html>

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: