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_partitioner
def 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_partitioner
def 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] += 1
repeats = [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] += 1
repeats = [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 tuple
def 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()
No comments:
Post a Comment