A bit of CS philosophy if you may... On Monday 26 Oct 2009 18:41:23 Jim Gibson wrote: > On 10/26/09 Mon Oct 26, 2009 8:45 AM, "Michael Alipio" > > <daem0n...@yahoo.com> scribbled: > > Thanks for the advice. Forgive me if I sounded like someone who's > > frustrated, couldn't do his homework asking somebody else for help. > > > > When I was learning C programming, I read that learning those difficult > > algorithms such as bubble sort, quick sort, binary search, is something > > that only programming students have to deal with. > > Those are not difficult algorithms. They are algorithms that any programmer > should know. If you are learning how to program, then you are a > "programming student". However, generating a complete set of permutations > efficiently for any size set IS a difficult algorithm. > > > I knew I needed a recursive function, I just didn't know how to start. > > What confused me more is that the code I found is a lot different from > > what I was initially thinking. He used the builtin function substr in the > > code in a way that I couldn't figure how it worked. > > You don't "need" a recursive function. Using a recursive function can > sometimes be an elegant method for solving a difficult problem. However, > alternate solutions not using recursive functions can always be found. >
One thing I should note is that from my understanding of theoretical or pseudo-theoretical computer science, a function or routine that just uses its own stack to do tree-recursion, is still recursive, only it is not *procedurally-recursive*. Often, people use such techniques of doing a recursion without a procedure that calls itself directly or indirectly, when writing programs in hardware-design languages such as VHDL or Verilog (or so I was told - I have little serious experience with them myself), or in languages that do not support such recursion (such as COBOL or old versions of Fortran), but it is a useful in languages that do support such recursion too. In one of my C libraries ( http://fc-solve.berlios.de/ to be specific) I ended up porting a procedurally recursive Depth-First Search ( http://en.wikipedia.org/wiki/Depth-first_search ) algorithm to one that used my own dedicated stack of items, in order to save on CPU stack space, which is limited, especially the Windows' default. It turned out to be beneficial because that way I could do a constant time ( O(1) ) suspend and resume of the algorithm without resorting to setjmp/longjmp games (which I naturally would prefer to avoid). In some languages (most notably Scheme), proper tail recursion is implemented using an implicit goto. So the following Perl program when translated to Scheme: sub print_loop { my ($i) = @_; print "I is now $i\n"; if ($i == 0) { return; } else { return print_loop($i-1); } } Would be equivalent to: sub print_loop { my ($max_i) = @_; foreach my $i (reverse(0 .. $max_i)) { print "I is now $i\n"; } return; } You can achieve a similar effect in Perl explicitly using "goto &subname;" but I wouldn't recommend it. From what I understood, the Perl's recursion stack (and all the other stacks used by the Perl back-end) are implemented on the process heap so they cannot overflow the process stack, unless one recursively uses binary Perl-XS routines with Perl callbacks (e.g: those in List::Util or List::MoreUtils). Regards, Shlomi Fish > > See below: > > > > my $result = ''; > > > > perm(0,2); > > > > sub perm($$){ > > my ($cur,$max) = @_; > > > > if ($cur>=$max){ > > print "$result\n"; > > return; > > } > > > > for(@word){ > > substr($result,$cur,1)=$_; > > perm($cur+1,$max); > > } > > } > > > > What's the use of double ($$) after sub perm?? Does it have anything to > > do with process IDs (perldoc perlvar says so)? > > The ($$) is a function prototype indicating that the function accepts two > scalars. See 'perldoc perlsub' and search for 'Prototypes'. > > > This line is also confusing: > > substr($result,$cur,1)= $_; > > > > Substr returns a list, right? The first parameter is the expression, 2nd > > is the offset, and last is the length. > > The above line is too cryptic for me. What confused me more is that the > > return value of substr was assigned the $_. > > No, substr returns a scalar. It can also return an lvalue if its first > argument is an lvalue, as is being done in this case. This allows you to > assign to a subset of a string scalar the value appearing to the right of > the equal sign ($_), thereby replacing part of the string. You can perform > the same function by including the replacement part as a fourth argument to > substr. See 'perldoc -f substr' for details. > -- ----------------------------------------------------------------- Shlomi Fish http://www.shlomifish.org/ "The Human Hacking Field Guide" - http://shlom.in/hhfg Chuck Norris read the entire English Wikipedia in 24 hours. Twice. -- To unsubscribe, e-mail: beginners-unsubscr...@perl.org For additional commands, e-mail: beginners-h...@perl.org http://learn.perl.org/
