Re: [PHP] who can do this without the recursion
On Tue, July 5, 2005 3:08 pm, Rene Brehmer said: Documented research indicate that on Tue, 5 Jul 2005 14:07:21 -0700 (PDT), Richard Lynch wrote: You'd think having done a zillion of these in my Grad School days would have made more of an impression... Mostly it impressed me that recursion wasn't cool -- just another tool and one that you only should pull out 1% of the time. When we learned about recursion it took our teacher 15 minutes to come up with an example for what the heck it was good for ... and it wasn't even a good one (can't remember what it was). There are some husband/wife functions in Mathematics/CS that are easiest to define recursively... I think there may even be proofs that certain functions CANNOT be expressed as iterations, but that's digging through 10-20 years old memories of courses I sometimes barely passed... I only use recursion when I need to output data stored in a tree format (you know, each child has a parent, each parent can have multiple children), otherwise I don't really know what to use recursion for. If you're willing to spend the extra storage space for next/prev fields, and if you INSERT/CHANGE less frequently than you OUTPUT, you can make a threaded tree where essentially you use the inherent tree structure to fairly quickly maintain a second path through the tree that's basically a linked list. Picture a tree that got TP'ed at Halloween, and you get the basic idea. :-) I had a CS prof in grad school that must have hated recursion and loved iteration, cuz we spent most of the semester converting recursive functions into iterative for homework. And, it must be admitted, the iterative solution was invariable MUCH faster, and the code to do it was a little bit more work, but seldom was it, like, totally gnarly. (To use the vernacular then current.) Mostly I have database queries where the results are built into 2-3 D arrays, and then used as the data the recursions work from ... found it to be the only way doing those trees fast when the data is variable and stored in a database... There was a HUGE long-ass thread/argument on PHP-General (or maybe it was just PHP back then) about Forum threads and whether they could be converted to iterative or not, with or without limiting the number of posts in a forum, with or without too much overhead in the SQL/DB/PHP code and storage space. It raged on for months, it seemed like, and quite a bit of inventive code and invective messages were posted. Several theories were shot down. I'm not sure anybody ever really got into it deep enough to build a threaded tree in SQL or anything like that... Since I had little interest in Forums, I only sorta followed the whole thread anyway... You may (or may not) find it useful if you can find the thread and read it. Something like forum thread limit recursion iteration in MARC might turn it up... If MARC goes back that far... -- Like Music? http://l-i-e.com/artists.htm -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
[PHP] who can do this without the recursion
hi everyone,
I have a function which recursively loops an assoc array in
order to build an HTML string containing hidden input elements
that repesent the key/values passed in the array ... I know this can
be done without recursion but I'm having a brainfreeze, anyone care
to share some tips on replacing the recursion with some kind of stack
based solution (the idea being that I want to remove the overhead
of the recursive calls to the function if possible ...
I'm looking to get a better understanding of alternatives to
recursion in general rather than in this specific example,
so come people show us what you can do! :-)
example:
function rec_build_hidden_inputs($args = array(), $prefix = '')
{
static $inputTpl = input type=hidden name=%s value=%s /\n;
$_contents = '';
foreach ($args as $key = $val) {
$nextPrefix = $prefix ''
? {$prefix}[{$key}];
: $key
;
$_contents .= is_array($val)
? rec_build_hidden_inputs($val, $nextPrefix)
: sprintf($inputTpl, $nextPrefix, $key)
;
}
return $_contents;
}
rgds,
Jochem
PS - do ya think I can copyright this?:
=
?
:
;
nah, didn't think so - none the less you might be surprised how many people
it annoys ;-)
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] who can do this without the recursion
= ? : ; nah, didn't think so - none the less you might be surprised how many people it annoys ;-) It annoys the hell out of me, but I can't help liking it at the same time...I am now really confused!!! -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] who can do this without the recursion
On Tue, July 5, 2005 3:48 am, Jochem Maas said: I have a function which recursively loops an assoc array in order to build an HTML string containing hidden input elements that repesent the key/values passed in the array ... I know this can be done without recursion but I'm having a brainfreeze, anyone care to share some tips on replacing the recursion with some kind of stack based solution (the idea being that I want to remove the overhead of the recursive calls to the function if possible ... I don't recall the answer, but if you Google for eliminate tail recursion or convert tail recursion to iteration you should find Computer Science textbook examples galore. You'd think having done a zillion of these in my Grad School days would have made more of an impression... Mostly it impressed me that recursion wasn't cool -- just another tool and one that you only should pull out 1% of the time. I have a hacksaw. I don't use it every meal. -- Like Music? http://l-i-e.com/artists.htm -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] who can do this without the recursion
Documented research indicate that on Tue, 5 Jul 2005 14:07:21 -0700 (PDT), Richard Lynch wrote: You'd think having done a zillion of these in my Grad School days would have made more of an impression... Mostly it impressed me that recursion wasn't cool -- just another tool and one that you only should pull out 1% of the time. When we learned about recursion it took our teacher 15 minutes to come up with an example for what the heck it was good for ... and it wasn't even a good one (can't remember what it was). I only use recursion when I need to output data stored in a tree format (you know, each child has a parent, each parent can have multiple children), otherwise I don't really know what to use recursion for. Mostly I have database queries where the results are built into 2-3 D arrays, and then used as the data the recursions work from ... found it to be the only way doing those trees fast when the data is variable and stored in a database... -- Rene Brehmer aka Metalbunny We have nothing to fear from free speech and free information on the Internet, but pop-up advertising! http://metalbunny.net/ My little mess of things... -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] who can do this without the recursion
On 5 Jul 2005, at 23:08, Rene Brehmer wrote: Mostly it impressed me that recursion wasn't cool -- just another tool and one that you only should pull out 1% of the time. When we learned about recursion it took our teacher 15 minutes to come up with an example for what the heck it was good for ... and it wasn't even a good one (can't remember what it was). I have a Sudoku solver that requires every single permutation of sets of numbers for testing against, which I find a recursive function generates extremely quickly. The main uses I find are, as stated before, for building trees of data or doing very abstract problem solving. Gaby -- Junkets for bunterish lickspittles since 1998! [EMAIL PROTECTED] http://weblog.vanhegan.net -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] who can do this without the recursion
On 7/5/05, Jochem Maas [EMAIL PROTECTED] wrote:
hi everyone,
I have a function which recursively loops an assoc array in
order to build an HTML string containing hidden input elements
that repesent the key/values passed in the array ... I know this can
be done without recursion but I'm having a brainfreeze, anyone care
to share some tips on replacing the recursion with some kind of stack
based solution (the idea being that I want to remove the overhead
of the recursive calls to the function if possible ...
I'm looking to get a better understanding of alternatives to
recursion in general rather than in this specific example,
so come people show us what you can do! :-)
example:
function rec_build_hidden_inputs($args = array(), $prefix = '')
{
static $inputTpl = input type=hidden name=%s value=%s /\n;
$_contents = '';
foreach ($args as $key = $val) {
$nextPrefix = $prefix ''
? {$prefix}[{$key}];
: $key
;
$_contents .= is_array($val)
? rec_build_hidden_inputs($val, $nextPrefix)
: sprintf($inputTpl, $nextPrefix, $key)
;
}
return $_contents;
}
rgds,
Jochem
PS - do ya think I can copyright this?:
=
?
:
;
nah, didn't think so - none the less you might be surprised how many people
it annoys ;-)
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
This is completely untested (sry, don't have the time right now to
test it), but something like this should work
$inputTpl = input type=hidden name=%s value=%s /\n;
$recursiveStack = array();
// change firstArgs and firstPrefix to the first values in your array
$firstArgs = array();
$firstPrefix = '';
$recursiveStack[] = array(args=$firstArgs, prefix=$firstPrefix);
$_contents = '';
while($currVal = array_pop($recursiveStack)) {
$args = $currVal[args];
$prefix = $currVal[prefix];
foreach($args as $key=$val) {
$nextPrefix = $prefix ''
? {$prefix}[{$key}];
: $key
;
if(is_array($val)) {
array_push($recursiveStack, array(args=$val,
prefix=$nextPrefix));
} else {
$contents .= sprintf($inputTpl, $nextPrefix, $key);
}
}
}
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
