Hello Brett,
Thank you for the information. I was ignorant about
the tail recursiveness. Indeed, this code does not
need stack. I guess I can replace 'tree(++x)' by
'++x; goto beginning_of_this_func;'. This is a smart
idea.
I didn't mean to run ROOT on Nokia, but just about
the portability of the recursive code in general.
Anyway, you explained this.
Thank you
Masaharu Goto
>Date: Sat, 23 Jun 2001 12:08:21 -0400 (EDT)
>From: Brett Viren <bv@bnl.gov>
>Reply-To: Brett Viren <bv@bnl.gov>
>To: Masaharu Goto <MXJ02154@nifty.ne.jp>
>Cc: onuchin@fnal.gov, roottalk@pcroot.cern.ch
>Subject: Re: RE:Re: [ROOT] bug&quest
>
>Masaharu Goto writes:
> >
> > However, I personally do not like this kind of programming.
> > Recursive call can waste physical resources. This small
> > example with a tiny job uses up very deep stack memory.
>
>Just an aside:
>
>The example is tail-recursive so it doesn't need to actually fill up
>the stack. It can be implemented by the interpreter as a loop. This
>is a common optimization in Scheme and Lisp interpreters. When an
>algorithm is inherently recursive, it seems to me that it's valid to
>want the code to be as well.
>
>To compare, note the one line addition to `tree()', below, kills
>tail-recursiveness and must fill up the stack. This is because state
>of each recursion must be stored until the recursion is finished.
>
>int tree(int x)
>{
> static int y=0;
> static int z=0;
> static int qq = printf("%5s","*");
>
> x = x>0 ? -9: x;
> z = (z=x+5)>0 ? z:-z;
> printf(!x&&++y ? "\n":(z?(z>y%3+y/3?" ":(x<-5 ?"/" :"\\")):"|"));
> int retval = (y-9) ? tree(++x) : printf(" _|_|_\n \\___/\n");
> fprintf(stderr,"Stack level: %d", x);//<--Kills tail-recursiveness
> return retval;
>}
>
>
> > This is mostly okey for PCs. But, imagine somebody wants
> > to put this nice picture on a small devices like celler phone
> > where every piece of physical resource is precious.
>
>Root on an iPaq I can believe, but Root on a Nokia?.....
>
>1-800-PHYSICS,
>-Brett.
This archive was generated by hypermail 2b29 : Tue Jan 01 2002 - 17:50:50 MET