[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: Offtopic: Re: recursion, stacksize & linux
From:       Lotzi Boloni <boloni () cplane ! com>
Date:       2000-12-12 16:36:43
[Download RAW message or body]

> I didn't have such a course, but I can imagine that it 
> is always possible (though not necesarilly trivial).
> 
> A recursion is, by definition, doing 'the same' over and
> over again until some end-value (predefined value, I do not
> know the correct terminology) is encountered.
> I think this could (almost) always be done in a 
> while( parameter != boundary_condition ) type loop.

  Yes, it is possible, remember that at the assembly level 
there is no real concept of recursion. However recursively you always have
a hidden datastructure, the stack. 

  The translation to non-recursive functions makes sense if you can
eliminate the use of the stack. It is not always possible (there are
problems which are demonstrably need O(n) space. 

  So what Michael said is that for the purpose of this discussion he does
not consider those cases when the conversion is possible, but explicitly
emulating the stack.

  There is another way of looking at this, in terms of
continuations - you need a list of the places where you need to restart
the computation - in this case the border of the already filled
region (for the recursive call, this is what you have in the stack). You
want to have an efficient description of it, and you want to
make it short. As this is a frequently used algorithm, a lot of clever
solutions were designed, so I guess we should just take one of them. 

          Lotzi

> 
> If such is not the case I would be interested why not.
> 
> Leon
> 
> David van Hoose wrote:
> > 
> > Michael Matz wrote:
> > >
> > > Hi,
> > >
> > > On Mon, 11 Dec 2000, David van Hoose wrote:
> > > >
> > > > How about transforming the recursive function to a loop?
> > >
> > > Looping and recursion are not equivalent, so this is not always
> > > possible. Generally only with tail recursion. (except of course you
> > > explicitely model the stack, which I don't consider transforming recursion
> > > to loops for this discussion).
> > 
> > Uhh.. Wrong. Take a discrete structures course at a university.
> > 
> > --
> > -Dave
> > 
> > >> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<
>  
> >> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<
> 

-- 
----------------------------------------------------
Lotzi Boloni 

boloni@cplane.com   http://www.geocities.com/boloni2
----------------------------------------------------

 
>> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<

[prev in list] [next in list] [prev in thread] [next in thread]