CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner: Re: [rietchel] Recursion issue: Edit Log



BillKSmith
Veteran

May 5, 2017, 8:59 PM


Views: 2440
Re: [rietchel] Recursion issue

Recursion can be confusing. It helps to pay as much attention to the design of your data structure as you do to the code. Document its design before you attempt to code. I have included the design spec in the comments of the code. Neither Laurent nor I have reproduced your output exactly because you have not made it clear how to choose the nodes to print (They are all leaves except a.c.e). I print only the 'leaves' of the tree. (Move the print statement out of the if-block if you wish to print every node.)


Code
use strict; 
use warnings;

# Data structure is defined recursively.
# TREE is a reference to a node
# NODE is a two element list
# 0: Value
# 1: Ref to an array (possibly empty) of trees.


my $sample_tree = [
'a',
[ [ 'b', [] ],
[ 'c',
[ [ 'e', [ [ 'h', [] ] ] ],
[ 'f', [] ],
[ 'g', [ [ 'h', [] ] ] ],
[ 'g', [ [ 'j', [] ] ] ]
]
],
[ 'd', [] ]
]
];

visit_all_nodes($sample_tree);
exit(0);

sub visit_all_nodes {
# Visit every node in the tree.
# If there are no sub-trees, print the "path" to the current node.
use 5.10.0;
use feature qw(state);
state @path;
my ($value, $ref_to_array_of_sub_trees) = @{shift()};
my $number_of_sub_trees = scalar @$ref_to_array_of_sub_trees;
push @path, $value;

if ( $number_of_sub_trees == 0 ) {
local $" = q(.); print "@{path}\n";
}
else{
visit_all_nodes($_) foreach @$ref_to_array_of_sub_trees;
}

pop @path;
return;
}

OUTPUT:
a.b
a.c.e.h
a.c.f
a.c.g.h
a.c.g.j
a.d


Notes:
The code is formatted with perltidy to make the definition of the tree as clear as possible.

The path is not passed as an argument. The variable @path is a 'state' variable. There is only one copy of it, which is available to every instance of the subroutine, but nowhere else.

The version requirement is to make sure that the state feature is available.

The special variable $" is used to add the periods which you show in your sample output.
Good Luck,
Bill

(This post was edited by BillKSmith on May 6, 2017, 3:49 AM)


Edit Log:
Post edited by BillKSmith (Veteran) on May 6, 2017, 3:49 AM


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives