Welcome to WebmasterWorld Guest from 54.211.222.233 register, free tools, login, search, pro membership, help, library, announcements, recent posts, open posts, Become a Pro Member
 Home / Forums Index / Code, Content, and Presentation / PHP Server Side Scripting
Forum Library, Charter, Moderators: coopster & jatar k

PHP Server Side Scripting Forum

 Tweet
Recursion, especially in PHP
Anyone know details for implementation?
ergophobe

Msg#: 1160 posted 8:09 pm on Sep 13, 2002 (gmt 0)

This picks up on a comment regarding recursion in post on ACSII key generation [webmasterworld.com] (please ignore the first script I posted. I cut and pasted the wrong version into the post). It's off-topic in that post, but an issue that interests me, so I wanted to start a new thread and hopefully bring some other folks into it.

This was really brought home to me while working my way through Abelson and Sussman's Structure and Interpretation of Computer Programs [mitpress.mit.edu], usually known as SICP. A great book if you haven't read it.

If you have programmed in Scheme (the language in SICP), you know that there is no looping structure. All looping is done by recursion (see the example at the end). After doing a lot of these programs, I came to see how powerful this technique is and how sometimes it can greatly reduce the complexity of a problem. I was taught to mostly avoid recursion back in the early 1980s when I was learning Pascal and FORTRAN.

For example in Scheme, a function that uses linear recursion [mitpress.mit.edu] will result in high memory usage, but something that uses iterative recursion (see reference to "linear recursion") will use an essentially constant amount of memory. For the computer geeks... this means that for a linearly recursive process with an input n, the number of steps and the space required will grow as Theta(n), while for an iteratively recursive process, the number of steps will grow as Theta(n) memory, but the space required will grow as Theta(1), in other words it will be constant (See SICP on Orders of Growth [mitpress.mit.edu]). A Scheme interpreter must behave this way to be considered compliant.

So here's the question: Does anyone know how PHP (or PERL for that matter) implements recursion? Does it have good garbage collection? Will an iteratively recursive process of input n grow as T(1) or T(n) in PHP? Is there any reason to avoid recursion in PHP?

This was running through my head as I was writing the script that I posted in the other thread ACSII key generation [webmasterworld.com] and my initial tests showed very low memory usage when I ran it, but that's not with serious benchmarking tools. I'd be curious whether anyone had some solid information and thoughts.

-------- EXAMPLE CODE -----------
#1 - written the normal PHP way

for (\$i=0; \$i<10000; \$i++) {
\$sum = \$sum+\$i;
}
return \$sum;

#2 written the Scheme *way* (but still *in* PHP)

function sum_series (\$sum, \$i) {
\$sum = \$sum + \$i;
if (\$i>=10000) {
return \$sum;
}else{
return sum_series(\$sum, (\$i+1);
}

Since there is nothing to remember - that is the calculation is not dependent on the value returned from the function - good garbage collection would reclaim used memory.

This of course is a somewhat stupid example where there's no reason to use recursion, but merely to show how the type of program that would have a small memory footprint using recursion.

----------------- END EXAMPLE -----------------

Tom

Nick_W

Msg#: 1160 posted 8:14 pm on Sep 13, 2002 (gmt 0)

Recursion is well tricky!

But PHP handles it very well, if you're usiong an array for example, you'll probably need to use something like array_unique() to get rid of the unwanted stuff....

Never have much call to use it in the general course of my work but the one time I did it was pretty straight forward...

Nick

bird

Msg#: 1160 posted 8:35 pm on Sep 13, 2002 (gmt 0)

With functional languages (lisp and scheme, but also some others), the compilers often use an optimization technique called "tail call elimination". In practise, this means that recursive function calls are internally converted into an iteration. Of course, this only works for relatively simple functions, but those tend to be the rule in those languages.

With languages of a more procedural character, this optimization is not quite as prevalent. Note that garbage collection won't really help you, as it can only kick in after returning from the recursion. As long as you're deep down in the umpteenth call, all the stack frames need to remain intact. Your example is *very* simple, so that 10k calls probably just don't reach the critical limits of PHP.

Did you compare the execution times? Languages can vary greatly in the overhead necessary to call a function. In any case, if the number of levels gets higher than a rather small figure (depending on the problem, probably in the hundreds), I would try to avoid recursion. Even with the abundance of RAM on todays computers, the risk of a memory error as well as the performance impact often aren't worth the simplification of a recursive solution.

andreasfriedrich

Msg#: 1160 posted 10:21 pm on Sep 13, 2002 (gmt 0)

My "aversion to recursion" as you so nicely put it stems from my days as a Visual Basic programmer. I had to traverse rather large hierarchical structures and do a lot of rather complicated calculations. This was obviously to much for VB6. Firstly the overhead in calling a function slowed down the whole process and secondly there were times when the programs terminated with a stack overflow. I had to resort to using loops.

I still tend to do quite a lot things the looping way, especially if I cannot predict the depth of recursion. I never benchmarked both approaches for a given problem in Perl. So most often itīs not a decision based on hard facts which way I do it. And itīs just a matter of experience. While I have no difficulties grasping the concept of recursion and recursion solves quite a few things far easier than the loop approach I tend to think that that a lot of problems where people use recursion are better solved using looping.

 "aversion to recursion" (couldn't resist the alliteration)

If I remember those Latin lessons in High School correctly, this figure of speech is not an alliteration but a homoioteleuton.

alliteration
repetition of the same sound at the beginning of two or more words

homoioteleuton
repetition of the same sound at the ending of two or more adjacent or parallel words

Do not confuse homoioteleuton with homoioptoton (repetition of similar case endings in adjacent or parallel words) which can only be used with inflected languages

ergophobe

Msg#: 1160 posted 10:26 pm on Sep 13, 2002 (gmt 0)

Bird, thanks for the response. I've been wanting to get a discussion going on this for a long time because i can't find any decent info on PHP on the net in this regard. I've been too lazy, but finally got inspired by Andreas.

[edit: Andreas - you posted while I was writing this. I'll read it and respond, but thanks in advance]

I am responding out of order because I want to keep the stuff I'm most intersted in near the top.

 Note that garbage collection won't really help you, as it can only kick in after returning from the recursion. As long as you're deep down in the umpteenth call, all the stack frames need to remain intact.

That's my real question. In Scheme or another language that fully supports tail recursion, garbage collection would kick in as soon as you made the first recursive call (i.e. when you entered the function for the second time, it would use the garbage collection mechanism to reclaim the memory used during the initial call to the function). So inother words, in PHP you think (or perhaps know) that this won't be the case?

Well, yes. As I said, I would never use recursion for that sort of thing. It was the simplest example I could think of for people who have never seen Scheme or Lisp. There are lots of cases, however, when a recursive solution is much better than a looping solution (rather than recursive vs iterative, because as SICP points out, many recursive functions can yield iterative processes).

The thread got inspired by the discussion on creating sequential ASCII keys [webmasterworld.com], where the script I posted was somewhat more complex and more typical of a situation where I think a recursive solution would be appropriate. The original poster mentioned Huffman encoding [mitpress.mit.edu], which is an application where it's hard to beat recursion for simplest solution.

 "tail call elimination"

I know this is required for an interpreter to be considered compliant with the Scheme standard, but I wasn't sure how common it is for modern languages to implement it. So basically you're saying that even modern procedural languages will be worse at this than Scheme or Lisp?

 In practise, this means that recursive function calls are internally converted into an iteration.

That's the idea behind the distinction between "linear" and "iterative" recursion that I mentioned. Often a recurisve function actually is an iterative process (I don't think it's quite true that it's "converted" into an iteration). Quite frequently, you can achieve that by passing an additional parameter.

 only works for relatively simple functions

Is that really true? The idea of tail recursion as I understand it is that the recursion call is the *last* thing in the function - i.e. no more processing needs to be done based on the value returned. Otherwise put, the call comes at the "tail" of the function. This doesn't necessarily mean the function must be *simple*, but it does mean that certain processes can't be done this way and the interpreter (in Scheme) won't be able to reclaim the memory until the end criterion is met and all values are passed up the recursion tree.

Cheers,

Tom

ergophobe

Msg#: 1160 posted 10:35 pm on Sep 13, 2002 (gmt 0)

 I tend to think that that a lot of problems where people use recursion are better solved using looping.

Undoubtedly correct and I would say that you could say the contrary as well (many solutions solved by looping are better solved with iteration). Incidentally, the first solution that I wrote for the ASCII key question actually was iterative. I've been wanting to get a discussion on recursion in PHP going for a while, though, so that's why I made the second solution.

 Firstly the overhead in calling a function slowed down the whole process and secondly there were times when the programs terminated with a stack overflow.

If I find some spare time, I'll try to benchmark some looped vs recursive solutions. I was curious what experience people had had.

Thanks for the vocabularly and Latin lesson. I love it!

Tom

bird

Msg#: 1160 posted 11:53 pm on Sep 13, 2002 (gmt 0)

garbage collection would kick in as soon as...

Most GCs are non-deterministic. The moment that a variable goes out of scope, that just means that it *can* be collected then. In reality, it will rather be collected when the GC "gets around to it". Typically, this is either after a fixed number of instructions, when memory gets tight, or when the programmer explicitly invokes a collection run.

required for an interpreter to be considered compliant with the Scheme standard

That's actually not something that belongs into a language standard, and I'd expect many implementations to ignore this point. The main reason why it often *is* implemented in scheme (and other strongly functional languages) is the fact that recursive functions are so popular there. Once you know that most of your users will be using recursion all the time, it's simply worth the effort to optimize recursion.

I don't know what kind of compilation overhead is involved, but I assume that none of the modern bytecode interpreted languages (Perl, Python, PHP, Java) uses tail call elimination. I think it's already very rare for C compilers (let alone C++). Actually implementing it in a compiler it probably a lot trickier than the relatively simple concept makes it loo like.

Often a recurisve function actually is an iterative process

I think we're discussing on two different levels here. There are processes (often based on data structures) that have an inherently iterative or recursive character. And then there are functions that are implemented either iteratively or recursively. I believe that whether either type of process is implemented by the same type of function is generally open to programmers choice. Of course, the matching implementation will usually result in simpler code.

>>only works for relatively simple functions

Is that really true?

In this context, "simple" means that the recursive call must be at the end (="tail") of the function, and the function must be free of side effects. As soon as there are some trailing instructions after that call, or there's even a choice of several recursion paths, rewriting the result in an iterative manner gets extremely hairy (if it's even possible, I'm not a compiler guy).

On the positive side, where it is possible, the tail call elimination will also eliminate the need for GC. The compiler is only assigning a new value to a variable in each iteration, after all. The recursive instances of your original function have been flattened to a normal loop. Thinking about it, the recursive implementation also isn't subject to collection, as everything happens on the stack anyway.

homoioteleuton

Sounds greek to me (the dictionary confirms that: it was adapted as a foreign word by the romans).

andreasfriedrich

Msg#: 1160 posted 12:10 am on Sep 14, 2002 (gmt 0)

When I referred to the Latin lessons I did not say nor did I intend to imply that the words were Latin. However short of being taught ancient Greek in school in Germany (a fact bemoaned by many) and becoming real classicists most students have to make do with Latin. ;) As a consequence those rhetoric figures are taught in Latin since as you pointed out both words and style were adapted and in the case of rhetorics perfected by the romans.

homoioptoton
homios = like
ptosis = case

homoioteleuton
homios = like
teleute = ending

bird

Msg#: 1160 posted 12:28 am on Sep 14, 2002 (gmt 0)

Oh, of course it's latin. Just as words like "kindergarden" and "sauerkraut" are english... ;)

andreasfriedrich

Msg#: 1160 posted 12:39 am on Sep 14, 2002 (gmt 0)

... and le waldsterben is French ;)

ergophobe

Msg#: 1160 posted 12:42 am on Sep 14, 2002 (gmt 0)

Bird,

Thanks again for the long response. I think that pretty much wraps up the questions I had. One thing I can add though...

 That's actually not something that belongs into a language standard,

Perhaps not, but I quote from the Revised(5) Report on the Algorithmic Language Scheme [schemers.org], (20 Feb 1988), Section 1.1 [schemers.org]

 Implementations of Scheme are required to be properly tail-recursive. This allows the execution of an iterative computation in constant space, even if the iterative computation is described by a syntactically recursive procedure. Thus with a properly tail-recursive implementation, iteration can be expressed using the ordinary procedure-call mechanics, so that special iteration constructs are useful only as syntactic sugar.

Cheers,

Tom

 Global Options: top home search open messages active posts  Tweet

 Home / Forums Index / Code, Content, and Presentation / PHP Server Side Scripting