## Monday, March 9, 2009

### Higher Order Perl (Python Style) : Chapter 5 - From Recursion To Iterators

TOC
`### Chapter 5 - From Recursion To Iterators### 5.1 The Partition Problem Revisited# sub find_share {#   my (\$target, \$treasures) = @_;#   return [] if \$target == 0;#   return    if \$target < 0 || @\$treasures == 0;#   my (\$first, @rest) = @\$treasures;#   my \$solution = find_share(\$target-\$first, \@rest);#   return [\$first, @\$solution] if \$solution;#   return         find_share(\$target       , \@rest);# }def find_share(target, treasures):    if target == 0:        return []    if target < 0 or len(treasures) == 0:        return    first, rest = treasures[0], treasures[1:]    solution = find_share(target-first, rest)    if solution != None:        return [first] + solution    return find_share(target, rest)# sub partition {#   my (\$target, \$treasures) = @_;#   return [] if \$target == 0;#   return () if \$target < 0 || @\$treasures == 0;#   my (\$first, @rest) = @\$treasures;#   my @solutions = partition(\$target-\$first, \@rest);#   return ((map {[\$first, @\$_]} @solutions),#          partition(\$target, \@rest));# }def partition(target, treasures):    if target == 0:        return [[]]    if target < 0 or len(treasures) == 0:        return []    first, rest = treasures[0], treasures[1:]    solutions = partition(target-first, rest)    return [[first] + solution for solution in solutions] + partition(target, rest)# sub make_partitioner {#   my (\$n, \$treasures) = @_;#   my @todo = [\$n, \$treasures, []];#   sub {#     while (@todo) {#       my \$cur = pop @todo;#       my (\$target, \$pool, \$share) = @\$cur;#       if (\$target == 0) { return \$share }#       next if \$target < 0 || @\$pool == 0;#       my (\$first, @rest) = @\$pool;#       push @todo, [\$target-\$first, \@rest, [@\$share, \$first]],#                   [\$target       , \@rest,   \$share         ];#     }#     return undef;#   } # end of anonymous iterator function# } # end of make_partitionerdef make_partitioner(n, treasures):    todo = [[n, treasures, []]]    while todo:        target, pool, share = todo.pop()        if target == 0:            yield share            continue        if target < 0 or len(pool) == 0:            continue        first, rest = pool[0], pool[1:]        todo.append([target-first, rest, share+[first]])        todo.append([target,       rest, share])# sub make_partitioner {#   my (\$n, \$treasures) = @_;#   my @todo = [\$n, \$treasures, []];#   sub {#     while (@todo) {#       my \$cur = pop @todo;#       my (\$target, \$pool, \$share) = @\$cur;#       if (\$target == 0) { return \$share }#       next if \$target < 0 || @\$pool == 0;#       my (\$first, @rest) = @\$pool;#       push @todo, [\$target, \@rest, \$share ] if @rest;#       if (\$target == \$first) {#          return [@\$share, \$first];#       } elsif (\$target > \$first && @rest) {#          push @todo, [\$target-\$first, \@rest, [@\$share, \$first]],#       }#     }#     return undef;#   } # end of anonymous iterator function# } # end of make_partitionerdef make_partitioner(n, treasures):    todo = [[n, treasures, []]]    while todo:        target, pool, share = todo.pop()        if target == 0:            yield share            continue        if target < 0 or len(pool) == 0:            continue        first, rest = pool[0], pool[1:]        if rest:            todo.append([target, rest, share])        if target == first:            yield share+[first]        elif (target > first and rest):            todo.append([target-first, rest, share+[first]])### 5.2 How to Convert a Recursive Function to an Iterator# sub rec {#   my (\$n, \$k) = @_;#   print \$k x \$n, "\n";#   for (1 .. \$n-1) {#     rec(\$n-\$_, \$_);#   }# }def rec(n, k):    print str(k) * n    for i in range(1,n):        rec(n-i, i)# sub partition {#   print "@_\n";#   my (\$n, @parts) = @_;#   for (1 .. \$n-1) {#     partition(\$n-\$_, \$_, @parts);#   }# }def partition(n, parts):    print [n] +parts    for i in range(1,n):        partition(n-i, [i]+parts)# for (@words) { \$seen{\$_}++ }# @repeats = grep \$seen{\$_} > 1, keys %seen;seen = {}for word in words:    seen.setdefault(word,[0])[0] += 1repeats = [word for word in seen if seen[word][0] > 1]# for (@words) { \$seen{lc \$_}++ }# @repeats = grep \$seen{\$_} > 1, keys %seen;seen = {}for word in words:    seen.setdefault(word.lower(),[0])[0] += 1repeats = [word for word in seen if seen[word][0] > 1]# sub partition {#   print "@_\n" if decreasing_order(@_);#   my (\$n, @parts) = @_;#   for (1 .. \$n-1) {#     partition(\$n-\$_, \$_, @parts);#   }# }def partition(n, parts):    if decreasing_order([n] +parts):        print [n] + parts    for i in range(1,n):        partition(n-i, [i]+parts)# sub partition {#   print "@_\n";#   my (\$largest, @rest) = @_;#   my \$min = \$rest[0] || 1;#   my \$max = int(\$largest/2);#   for (\$min .. \$max) {#     partition(\$largest-\$_, \$_, @rest);#   }# }def partition(largest, rest):    print [largest] + rest    min = (rest + [1])[0]    max = largest / 2    for i in range(min, max+1):        partition(largest-i, [i]+rest)# sub make_partition {  #   my \$n = shift;#   my @agenda = ([\$n,            # \$largest#                  [],            # \@rest#                  1,             # \$min#                  int(\$n/2),     # \$max#                 ]);#   return Iterator {#     while (@agenda) {#       my \$item = pop @agenda;#       my (\$largest, \$rest, \$min, \$max) = @\$item;#       for (\$min .. \$max) {#         push @agenda, [\$largest - \$_,          # \$largest#                        [\$_, @\$rest],           # \@rest#                        \$_,                     # \$min#                        int((\$largest - \$_)/2), # \$max#                       ];#       }#       return [\$largest, @\$rest];#     }#     return;#   };# }def make_partition(n):    agenda = [(n,   # largest               [],  # rest               1,   # min               n/2) # max              ]    while agenda:        (largest, rest, min, max) = agenda.pop()        for i in range(min, max+1):            agenda.append((largest - i,    # largest                           [i]+rest,       # rest                           i,              # min                           (largest-i)/2   # max                           ))        yield [largest]+rest# sub partition {#   my (\$largest, \$rest, \$min, \$max) = @_;#   for (\$min .. \$max) {#     partition(\$largest-\$_, [\$_, @\$rest], \$_, int((\$largest - \$_)/2));#   }#   return [\$largest, @\$rest];# }def partition(largest, rest, min, max):    for i in range(min, max+1):        partition(largest-i, [i]+rest, i, (largest-i)/2)    return [largest] + rest# sub make_partition {#   my \$n = shift;#   my @agenda = [\$n];#   return Iterator {#     while (@agenda) {#       my \$item = pop @agenda;#       my (\$largest, @rest) = @\$item;#       my \$min = \$rest[0] || 1;#       my \$max  = int(\$largest/2);#       for (\$min .. \$max) {#         push @agenda, [\$largest-\$_, \$_, @rest];#       }#       return \$item;#     }#     return;#   };# }def make_partition(n):    agenda = [[n,[]]]    while agenda:        largest, rest = agenda.pop()        min = (rest + [1])[0]        max = largest / 2        for i in range(min, max+1):            agenda.append([largest-i, [i]+rest])        yield [largest] + rest# sub make_partition {#   my \$n = shift;#   my @agenda = [\$n];#   return Iterator {#     return unless @agenda;#     my \$item = pop @agenda;#     my (\$largest, @rest) = @\$item;#     my \$min = \$rest[0] || 1;#     my \$max  = int(\$largest/2);#     for (\$min .. \$max) {#       push @agenda, [\$largest-\$_, \$_, @rest];#     }#     return \$item;#   };# }### we *do* keep the while loop in the python version### and it looks just like the previous solution# # Compare two partitions for preferred order# sub partitions {#   for my \$i (0 .. \$#\$a) {#     my \$cmp = \$b->[\$i] <=> \$a->[\$i];#     return \$cmp if \$cmp;#   }# }# lists and tuples will compare naturally # in the correct way (unless i'm missing something here)def partitions(a,b):    return cmp(a,b)# sub make_partition {#   my \$n = shift;#   my @agenda = [\$n];#   return Iterator {#     return unless @agenda;#     my \$item = pop @agenda;#     my (\$largest, @rest) = @\$item;#     my \$min = \$rest[0] || 1;#     my \$max  = int(\$largest/2);#     for (\$min .. \$max) {#       push @agenda, [\$largest-\$_, \$_, @rest];#     }#     @agenda = sort partitions @agenda;#     return \$item;#   };# }def make_partition(n):    agenda = [[n,[]]]    while agenda:        largest, rest = agenda.pop()        min = (rest + [1])[0]        max = largest / 2        for i in range(min, max+1):            agenda.append([largest-i, [i]+rest])        agenda.sort()        yield [largest] + rest### 5.3 A Generic Search Iterator# use Iterator_Utils 'Iterator';# sub make_dfs_search {#   my (\$root, \$children) = @_;#   my @agenda = \$root;#   return Iterator {#     return unless @agenda;#     my \$node = pop @agenda;#     push @agenda, \$children->(\$node);#     return \$node;#   };# }def make_dfs_search(root, children):    agenda = [root]        while agenda:        node = agenda.pop()        agenda.extend(children(node))        yield node# sub make_partition {#   my \$n = shift;#   my \$root = [\$n];#   my \$children = sub {#     my (\$largest, @rest) = @{shift()};#     my \$min = \$rest[0] || 1;#     my \$max  = int(\$largest/2);#     map [\$largest-\$_, \$_, @rest], (\$min .. \$max);#   };#   make_dfs_search(\$root, \$children);# }def make_partition(n):    root = [n]    def children(largest, rest):        min = (rest + [1])[0]        max = largest / 2        return [(largest-i, [i]+rest) for i in range(min, max+1)]    return make_dfs_search(root, children)# sub make_dfs_search {#    my (\$root, \$children, \$is_interesting) = @_;#    my @agenda = \$root;#    return Iterator {#      while (@agenda) {#        my \$node = pop @agenda;#        push @agenda, \$children->(\$node);#        return \$node if !\$is_interesting || \$is_interesting->(\$node);#      }#      return;#   };# }def make_dfs_search(root, children, is_interesting=None):    agenda = [root]        while agenda:        node = agenda.pop()        agenda.extend(children(node))        if is_interesting and is_interesting(node):            yield node# sub make_dfs_value_search {#   my (\$root, \$children, \$is_interesting, \$evaluate) = @_;#   \$evaluate = memoize(\$evaluate);#   my @agenda = \$root;#   return Iterator {#      while (@agenda) {#        my \$best_node_so_far = 0;#        my \$best_node_value = \$evaluate->(\$agenda[0]);#        for (0 .. \$#agenda) {#          my \$val = \$evaluate->(\$agenda[\$_]);#          next unless \$val > \$best_node_value;#          \$best_node_value = \$val;#          \$best_node_so_far = \$_;#       }#       my \$node = splice @agenda, \$best_node_so_far, 1;#       push @agenda, \$children->(\$node);#       return \$node if !\$is_interesting || \$is_interesting->(\$node);#     }#     return;#   };# }def make_dfs_value_search(root, children, is_interesting=None, evaluate=None):    if not is_interesting:        is_interesting = (lambda x: True)    if not evaluate:        evaluate = (lambda x: x)    agenda = [root]        while agenda:        node = agenda.pop()        agenda.extend(children(node))        if is_interesting(node):            yield node# sub make_dfs_search {#   my (\$root, \$children, \$is_interesting) = @_;#   my @agenda = \$root;#   return Iterator {#     while (@agenda) {#       my \$node = pop @agenda;#       push @agenda, reverse \$children->(\$node);#       return \$node if !\$is_interesting || \$is_interesting->(\$node);#     }#     return;#   };# }def make_dfs_search(root, children, is_interesting=None):    agenda = [root]        while agenda:        node = agenda.pop()        agenda.extend(reversed(children(node)))        if is_interesting and is_interesting(node):            yield node### 5.4 Other General Techniques for Eliminating Recursion# sub gcd {#   my (\$m, \$n) = @_;#   if (\$n == 0) {#     return \$m;#   }#   return gcd(\$n, \$m % \$n);# }def gcd(m,n):    if n == 0:        return m    return gcd(n, m % n)# sub gcd {#   my (\$m, \$n) = @_;#   until (\$n == 0) {#     (\$m, \$n) = (\$n, \$m % \$n);#   }#   return \$m;# }def gcd(m,n):    while n != 0:        m, n = n, m % n    return m# sub print_tree {#   my \$t = shift;#   return unless \$t;  # Null tree#   print_tree(\$t->left);#   print \$t->root, "\n";#   print_tree(\$t->right);# }def print_tree(t):    if not t:        return    print_tree(t.left)    print t.root    print_tree(t.right)# sub print_tree {#   my \$t = shift;#   while (\$t) {#     print_tree(\$t->left);#     print \$t->root, "\n";#     \$t = \$t->right;#   }# }def print_tree(t):    while t:        print_tree(t.left)        print t.root        t = t.right# sub print_tree {#   my \$t = shift;#   print_tree(\$t->left) if \$t->left;#   print \$t->root, "\n";#   print_tree(\$t->right) if \$t->right;# }def print_tree(t):    if t.left:        print_tree(t.left)    print t.root    if t.right:        print_tree(t.right)# sub print_tree {#   my \$t = shift;#   do {#     print_tree(\$t->left) if \$t->left;#     print \$t->root, "\n";#     \$t = \$t->right;#   } while \$t;# }def print_tree(t):    while t:        if t.left:            print_tree(t.left)        print t.root        t = t.right    # sub powerset_recurse (\$;@) {#     my ( \$set, \$powerset, \$keys, \$values, \$n, \$i ) = @_;#     if ( @_ == 1 ) { # Initialize.#         my \$null   = { };#         \$powerset  = { \$null, \$null };#         \$keys      = [ keys    %{ \$set } ];#         \$values    = [ values %{ \$set } ];#         \$nmembers  = keys %{ \$set };    # This many rounds.#         \$i         = 0;                  # The current round.#     }#     # Ready?#     return \$powerset if \$i == \$nmembers;#     # Remap.#     my @powerkeys    = keys   %{ \$powerset };#     my @powervalues = values %{ \$powerset };#     my \$powern      = @powerkeys;#     my \$j;#     for ( \$j = 0; \$j < \$powern; \$j++ ) {#         my %subset = ( );#         # Copy the old set to the subset.#         @subset{keys    %{ \$powerset->{ \$powerkeys  [ \$j ] } }} =#                 values %{ \$powerset->{ \$powervalues[ \$j ] } };#         # Add the new member to the subset.#         \$subset{\$keys->[ \$i ]} = \$values->[ \$i ];#         # Add the new subset to the powerset.#         \$powerset->{ \%subset } = \%subset;#     }#     # Recurse.#   powerset_recurse( \$set, \$powerset, \$keys, \$values, \$nmembers, \$i+1 );# }# we are stuck since python won't permit keys that aren't hashable# so instead of dicts of dicts i'll use set() with tuples.# we can easily go back to dicts from a set of tuples # but i may be missing some subtly important feature of this# algorithm.  but in any case it works.# also: this algorithm *seems* ridiculously unpythonic# _set: [(key,val)] # list of # powerset: [set([(key, val)])] # list of sets of tupledef powerset_recurse(_set, powerset=None, i=0):    # set up init stuff    if powerset == None:        powerset = [set()]    if i == len(_set):        return powerset    powerset_copy = copy.deepcopy(powerset)    ith_item = _set[i]    for subset in powerset_copy:       subset.add(ith_item)    powerset += powerset_copy    return powerset_recurse(_set, powerset, i+1)### uggg.  so that works, and *seems* very close### in principle to the original but I feel like### i didn't try hard enough to match the original style# sub powerset_recurse (\$) {#   my ( \$set ) = @_;#   my \$null = { };#   my \$powerset  = { \$null, \$null };#   my \$keys      = [ keys    %{ \$set } ];#   my \$values    = [ values %{ \$set } ];#   my \$nmembers  = keys %{ \$set };     # This many rounds.#   my \$i         = 0;                  # The current round.#   until (\$i == \$nmembers) {#     # Remap.#     my @powerkeys    = keys   %{ \$powerset };#     my @powervalues = values %{ \$powerset };#     my \$powern       = @powerkeys;#     my \$j;#     for ( \$j = 0; \$j < \$powern; \$j++ ) {#         my %subset = ( );#         # Copy the old set to the subset.#         @subset{keys    %{ \$powerset->{ \$powerkeys  [ \$j ] } }} =#                 values %{ \$powerset->{ \$powervalues[ \$j ] } };#         # Add the new member to the subset.#         \$subset{\$keys->[ \$i ]} = \$values->[ \$i ];#         # Add the new subset to the powerset.#         \$powerset->{ \%subset } = \%subset;#     }#      \$i++;#   }#   return \$powerset;# }def powerset_recurse(_set, powerset=None, i=0):    # set up init stuff    if powerset == None:        powerset = [set()]        while i < len(_set):        powerset_copy = copy.deepcopy(powerset)        ith_item = _set[i]        for subset in powerset_copy:           subset.add(ith_item)        powerset += powerset_copy        i += 1    return powerset# sub powerset_recurse (\$) {#     my ( \$set ) = @_;#     my \$null = { };#     my \$powerset  = { \$null, \$null };#     my \$keys      = [ keys    %{ \$set } ];#     my \$values    = [ values %{ \$set } ];#     my \$nmembers  = keys %{ \$set };     # This many rounds.#     for my \$i (0 .. \$nmembers-1) {#       #  Remap.#       my @powerkeys    = keys   %{ \$powerset };#       my @powervalues = values %{ \$powerset };#       my \$powern      = @powerkeys;#       my \$j;#       for ( \$j = 0; \$j < \$powern; \$j++ ) {#           my %subset = ( );#           # Copy the old set to the subset.#           @subset{keys    %{ \$powerset->{ \$powerkeys  [ \$j ] } }} =#                   values %{ \$powerset->{ \$powervalues[ \$j ] } };#           # Add the new member to the subset.#           \$subset{\$keys->[ \$i ]} = \$values->[ \$i ];#           # Add the new subset to the powerset.#           \$powerset->{ \%subset } = \%subset;#       }#     }#     return \$powerset;# }def powerset_recurse(_set, powerset=None, i=0):    # set up init stuff    if powerset == None:        powerset = [set()]        for i in range(len(_set)):        powerset_copy = copy.deepcopy(powerset)        ith_item = _set[i]        for subset in powerset_copy:           subset.add(ith_item)        powerset += powerset_copy    return powerset# sub powerset_recurse (\$) {#     my ( \$set ) = @_;#     my \$null = { };#     my \$powerset  = { \$null, \$null };#     while (my (\$key, \$value) = each %\$set) {#       # Remap.#       my @powerkeys    = keys   %{ \$powerset };#       my @powervalues = values %{ \$powerset };#       my \$powern      = @powerkeys;#       my \$j;#       for ( \$j = 0; \$j < \$powern; \$j++ ) {#           my %subset = ( );#           # Copy the old set to the subset.#           @subset{keys    %{ \$powerset->{ \$powerkeys [ \$j ] } }} =#                   values %{ \$powerset->{ \$powervalues[ \$j ] } };#           # Add the new member to the subset.#           \$subset{\$key} = \$value;#           # Add the new subset to the powerset.#           \$powerset->{ \%subset } = \%subset;#       }#     }#     return \$powerset;# }def powerset_recurse(_set):    powerset = [set()]        for ith_item in (_set):        powerset_copy = copy.deepcopy(powerset)        for subset in powerset_copy:           subset.add(ith_item)        powerset += powerset_copy    return powerset# sub binary {#   my (\$n) = @_;#   return \$n if \$n == 0 || \$n == 1;#   my \$k = int(\$n/2);#   my \$b = \$n % 2;#   my \$E = binary(\$k);#   return \$E . \$b;# }def binary(n):    if n in (0,1):        return str(n)    k = n / 2    b = n % 2    return binary(k) + str(b)# sub binary {#   my (\$n, \$RETVAL) = @_;#   \$RETVAL = "" unless defined \$RETVAL;#   my \$k = int(\$n/2);#   my \$b = \$n % 2;#   \$RETVAL = "\$b\$RETVAL";#   return \$RETVAL if \$n == 0 || \$n == 1;#   binary(\$k, \$RETVAL);# }def binary(n, retval=""):    k = n / 2    b = n % 2    retval = str(b)+retval    if n in (0,1):        return retval    return binary(k, retval)# sub binary {#    my (\$n, \$RETVAL) = @_;#    \$RETVAL = "";#    while (1) {#      my \$k = int(\$n/2);#      my \$b = \$n % 2;#      \$RETVAL = "\$b\$RETVAL";#      return \$RETVAL if \$n == 0 || \$n == 1;#     \$n = \$k;#   }# }def binary(n, retval=""):    while 1:        k = n / 2        b = n % 2        retval = str(b)+retval        if n in (0,1):            return retval        n = k# sub binary {#   my (\$n, \$RETVAL) = @_;#   \$RETVAL = "";#   while (1) {#     my \$b = \$n % 2;#     \$RETVAL = "\$b\$RETVAL";#     return \$RETVAL if \$n == 0 || \$n == 1;#     \$n = int(\$n/2);#   }# }def binary(n, retval=""):    while 1:        b = n % 2        retval = str(b)+retval        if n in (0,1):            return retval        n = n/2# sub factorial {#   my (\$n) = @_;#   return 1 if \$n == 0;#   return factorial(\$n-1) * \$n;# }def factorial(n):    if n == 0:        return 1    return factorial(n-1)*n# sub factorial {#   my (\$n, \$product) = @_;#   \$product = 1 unless defined \$product;#   return \$product if \$n == 0;#   return factorial(\$n-1, \$n * \$product);# }def factorial(n, product=1):    if n == 0:        return product    return factorial(n-1, n*product)# sub factorial {#   my (\$n) = @_;#   my \$product = 1;#   until (\$n == 0) {#     \$product *= \$n;#     \$n--;#   }#   return \$product;# }def factorial(n):    product = 1    while n != 0:        product *= n        n -= 1    return product# sub print_tree {#   my \$t = shift;#   do {#     print_tree(\$t->left) if \$t->left;#     print \$t->root, "\n";#     \$t = \$t->right;#   } while \$t;# }def print_tree(t):    while t:        if t.left:            print_tree(t.left)        print t.root        t = t.right# sub print_tree {#   my \$t = shift;#   my @STACK;#   do {#     push(@STACK, \$t), \$t = \$t->left if \$t->left;#     RETURN:#        print \$t->root, "\n";#     \$t = \$t->right;#   } while \$t;#   return unless @STACK;#   \$t = pop @STACK;#   goto RETURN;# }### this and the next couple examples### use GOTOs.  not much i can do about that.### if there is a way to simulate gotos in python### i'd be interested to hear it.# sub fib {#   my \$n = shift;#   if (\$n < 2) { return \$n }#   fib(\$n-2) + fib(\$n-1);# }def fib(n):    if n < 2:        return n    return fib(n-2) + fib(n-1)# sub fib {#   my \$n = shift;#   if (\$n < 2) {#     return \$n;#   } else {#     my \$s1 = fib(\$n-2);#     my \$s2 = fib(\$n-1);#     return \$s1 + \$s2;#   }# }def fib(n):    if n < 2:        return n    else:        s1 = fib(n-2)        s2 = fib(n-1)        return s1 + s2# sub fib {#   my \$n = shift;#   while (1) {#     if (\$n < 2) {#       return \$n;#     } else {#       my \$s1 = fib(\$n-2);#       my \$s2 = fib(\$n-1);#       return \$s1 + \$s2;#     }#   }# }def fib(n):    while 1:        if n < 2:            return n        else:            s1 = fib(n-2)            s2 = fib(n-1)            return s1 + s2# sub fib { #   my \$n = shift;#   my (\$s1, \$s2, \$return);#   while (1) {#     if (\$n < 2) {#       return \$n;#     } else {#       if (\$BRANCH == 0) {#         \$return = fib(\$n-2);#       } elsif (\$BRANCH == 1) {#         \$s1 = \$return;#         \$return = fib(\$n-1);#       } elsif (\$BRANCH == 2) {#         \$s2 = \$return;#         \$return = \$s1 + \$s2;#       }#     }#   }# }def fib(n):    BRANCH = 0    while 1:        if n < 2:            return n        else:            if BRANCH == 0:                _return = fib(n-2)            elif BRANCH == 1:                s1 = _return                _retrun = fib(n-2)            elif BRANCH == 2:                s2 = _return                _return = s1 + s2    return _return# sub fib {#   my \$n = shift;#   my (\$s1, \$s2, \$return);#   my \$BRANCH = 0;#   while (1) {#     if (\$n < 2) {#       return \$n;#     } else {#       if (\$BRANCH == 0) {#          \$return = fib(\$n-2);#       } elsif (\$BRANCH == 1) {#          \$s1 = \$return;#          \$return = fib(\$n-1);#       } elsif (\$BRANCH == 2) {#          \$s2 = \$return;#          \$return = \$s1 + \$s2;#       }#     }#   }# }def fib(n):    BRANCH = 0    while 1:        if n < 2:            return n        else:            if BRANCH == 0:                _return = fib(n-2)            elif BRANCH == 1:                s1 = _return                _return = fib(n-1)            elif BRANCH == 2:                s2 = _return                _return = s1 + s2    return _return# sub fib {#   my \$n = shift;#   my (\$s1, \$s2, \$return);#   my \$BRANCH = 0;#   while (1) {#     if (\$n < 2) {#       \$return = \$n;#     } else {#       if (\$BRANCH == 0) {#         \$return = fib(\$n-2);#       } elsif (\$BRANCH == 1) {#         \$s1 = \$return;#         \$return = fib(\$n-1);#       } elsif (\$BRANCH == 2) {#         \$return = \$s1 + \$s2;#       }#     }#   }# }def fib(n):    BRANCH = 0    while 1:        if n < 2:            _return = n        else:            if BRANCH == 0:                _return = fib(n-2)            elif BRANCH == 1:                s1 = _return                _return = fib(n-1)            elif BRANCH == 2:                _return = s1 + s2    return _return# sub fib {#   my \$n = shift;#   my (\$s1, \$s2, \$return);#   my \$BRANCH = 0;#   my @STACK;#   while (1) {#     if (\$n < 2) {#       \$return = \$n;#     } else {#       if (\$BRANCH == 0) {#         push @STACK, [ \$BRANCH, \$s1, \$s2, \$n ];#         \$n -= 2;#         \$BRANCH = 0;#         next;#       } elsif (\$BRANCH == 1) {#         \$s1 = \$return;#         push @STACK, [ \$BRANCH, \$s1, \$s2, \$n ];#         \$n -= 1;#         \$BRANCH = 0;#         next;#       } elsif (\$BRANCH == 2) {#         \$s2 = \$return;#         \$return = \$s1 + \$s2;#       }#     }#   }# }def fib(n):    BRANCH = 0    STACK = []    while 1:        if n < 2:            _return = n        else:            if BRANCH == 0:                STACK.append([BRANCH, s1, s2, n])                n -= 2                BRANCH = 0                continue            elif BRANCH == 1:                s1 = _return                STACK.append([BRANCH, s1, s2, n])                n -= 1                BRANCH = 0                continue            elif BRANCH == 2:                s2 = _return                _return = s1 + s2    return _return# sub fib {#   my \$n = shift;#   my (\$s1, \$s2, \$return);#   my \$BRANCH = 0;#   my @STACK;#   while (1) {#     if (\$n < 2) {#       \$return = \$n;#     } else {#       if (\$BRANCH == 0) {#         push @STACK, [ \$BRANCH, \$s1, \$s2, \$n ];#         \$n -= 2;#         \$BRANCH = 0;#         next;#       } elsif (\$BRANCH == 1) {#         \$s1 = \$return;#         push @STACK, [ \$BRANCH, \$s1, \$s2, \$n ];#         \$n -= 1;#         \$BRANCH = 0;#         next;#       } elsif (\$BRANCH == 2) {#         \$s2 = \$return;#         \$return = \$s1 + \$s2;#     }#   }#   return \$return unless @STACK;#   (\$BRANCH, \$s1, \$s2, \$n) = @{pop @STACK};#   \$BRANCH++;# }def fib(n):    BRANCH = 0    STACK = []    while 1:        if n < 2:            _return = n        else:            if BRANCH == 0:                STACK.append([BRANCH, s1, s2, n])                n -= 2                BRANCH = 0                continue            elif BRANCH == 1:                s1 = _return                STACK.append([BRANCH, s1, s2, n])                n -= 1                BRANCH = 0                continue            elif BRANCH == 2:                s2 = _return                _return = s1 + s2    if not STACK:        return _return    (BRANCH, s1, s2, n) = STACK.pop()    BRANCH += 1# sub fib {#   my \$n = shift;#   my (\$s1, \$s2, \$return);#   my \$BRANCH = 0;#   my @STACK;#   while (1) {#     if (\$n < 2) {#       \$return = \$n;#     } else {#       if (\$BRANCH == 0) {#         push @STACK, [ \$BRANCH, 0, \$s2, \$n ];#         \$n -= 2;#         next;#       } elsif (\$BRANCH == 1) {#         push @STACK, [ \$BRANCH, \$return, \$s2, \$n ];#         \$n -= 1;#         \$BRANCH = 0;#         next;#       } elsif (\$BRANCH == 2) {#         \$s2 = \$return;#       \$return = \$s1 + \$s2;#     }#   }#   return \$return unless @STACK;#   (\$BRANCH, \$s1, \$s2, \$n) = @{pop @STACK};#   \$BRANCH++;# }def fib(n):    BRANCH = 0    STACK = []    while 1:        if n < 2:            _return = n        else:            if BRANCH == 0:                STACK.append([BRANCH, 0, s2, n])                n -= 2                BRANCH = 0                continue            elif BRANCH == 1:                s1 = _return                STACK.append([BRANCH, _return, s2, n])                n -= 1                BRANCH = 0                continue            elif BRANCH == 2:                s2 = _return                _return = s1 + s2    if not STACK:        return _return    (BRANCH, s1, s2, n) = STACK.pop()    BRANCH += 1# sub fib {#   my \$n = shift;#   my (\$s1, \$return);#   my \$BRANCH = 0;#   my @STACK;#   while (1) {#     if (\$n < 2) {#       \$return = \$n;#     } else {#       if (\$BRANCH == 0) {#         push @STACK, [ \$BRANCH, 0, \$n ];#         \$n -= 2;#         next;#       } elsif (\$BRANCH == 1) {#         push @STACK, [ \$BRANCH, \$return, \$n ];#         \$n -= 1;#         \$BRANCH = 0;#         next;#       } elsif (\$BRANCH == 2) {#         \$return += \$s1;#       }#     }#     return \$return unless @STACK;#     (\$BRANCH, \$s1, \$n) = @{pop @STACK};#     \$BRANCH++;#   }# }def fib(n):    BRANCH = 0    STACK = []    while 1:        if n < 2:            _return = n        else:            if BRANCH == 0:                STACK.append([BRANCH, 0, n])                n -= 2                continue            elif BRANCH == 1:                STACK.append([BRANCH, _return, n])                n -= 1                BRANCH = 0                continue            elif BRANCH == 2:                _return += s1        if not STACK:            return _return        (BRANCH, s1, s2, n) = STACK.pop()        BRANCH += 1# sub fib {#   my \$n = shift;#   my (\$s1, \$return);#   my \$BRANCH = 0;#   my @STACK;#   while (1) {#   if (\$n < 2) {#     \$return = \$n;#   } else {#     if (\$BRANCH == 0) {#       push (@STACK, [ \$BRANCH, 0, \$n ]), \$n -= 1 while \$n >= 2;#       \$return = \$n;#     } elsif (\$BRANCH == 1) {#       push @STACK, [ \$BRANCH, \$return, \$n ];#       \$n -= 2;#       \$BRANCH = 0;#       next;#     } elsif (\$BRANCH == 2) {#       \$return += \$s1;#     }#   }#   return \$return unless @STACK;#   (\$BRANCH, \$s1, \$n) = @{pop @STACK};#   \$BRANCH++;# }def fib(n):    BRANCH = 0    STACK = []    while 1:        if n < 2:            _return = n        else:            if BRANCH == 0:                STACK.append([BRANCH, 0, n])                while n >= 2:                    n =- 1                _return = n            elif BRANCH == 1:                STACK.append([BRANCH, _return, n])                n -= 2                BRANCH = 0                continue            elif BRANCH == 2:                _return += s1        if not STACK:            return _return        (BRANCH, s1, n) = STACK.pop()        BRANCH += 1# sub fib {#   my \$n = shift;#   my (\$s1, \$return);#   my \$BRANCH = 0;#   my @STACK;#   while (1) {#     if (\$n < 2) {#       \$return = \$n;#     } else {#       if (\$BRANCH == 0) {#         push (@STACK, [ 1, 0, \$n ]), \$n -= 1 while \$n >= 2;#         \$return = \$n;#       } elsif (\$BRANCH == 1) {#         push @STACK, [ 2, \$return, \$n ];#         \$n -= 2;#         \$BRANCH = 0;#         next;#       } elsif (\$BRANCH == 2) {#         \$return += \$s1;#       }#     }#     return \$return unless @STACK;#     (\$BRANCH, \$s1, \$n) = @{pop @STACK};#   }# }# NOTE: I got lazy/confused by the end of this chapter so#       so these last few "fib" functions are not tested#       But it was an interesting discussion on "unfolding"#       recursion.def fib(n):    BRANCH = 0    STACK = []    while 1:        if n < 2:            _return = n        else:            if BRANCH == 0:                while n >= 2:                    STACK.append([1, 0, n])                    n =- 1                _return = n            elif BRANCH == 1:                STACK.append([2, _return, n])                n -= 2                BRANCH = 0                continue            elif BRANCH == 2:                _return += s1        if not STACK:            return _return        (BRANCH, s1, n) = STACK.pop()`