Recursion Optimization

[Andreas Schwab]

Kevin Atkinson <kevinatk@home.com> writes:

|> On 16 Aug 1999, Andreas Schwab wrote:
|> 
|> > Kevin Atkinson <kevinatk@home.com> writes:
|> > 
|> > |> Does gcc optimize in any way to minimize the cost of recursive functions
|> > |> calls.  In particular:
|> > |> 
|> > |> ONE:
|> > |> 
|> > |> Does gcc optimize tail recursive functions into simple loops?
|> 
|> You never answered this question.

Because I don't know the answer.  I do not know everything.

|> > |> TWO: 
|> > |> 
|> > |> In a function call like this:
|> > |> 
|> > |> int sum(int i, int stop) {
|> > |> }
|> > 
|> > This is not a tail recursive function.
|> 
|> I know.
|> 
|> > |> Will gcc recognize that the value of the second parameter never changes
|> > |> so that it can avoid allocating multiple copies of it on the stack.
|> > 
|> > This cannot be avoided.
|> 
|> What do you mean, cannot.  

How can you provide a contiguous argument list on the stack for the
recursive call without the copy?

|> Gcc can handel nested functions, so with a smart enough optimization
|> technoligy it out to be able to rewrite it as
|> 
|> int sum (int i, int stop) {
|>   int sumh(int i) {
|>     if (i == stop) return i;
|>     else return sum(i+1, stop) + i;
|>   }
|>   return sumh(i);
|> }

In which way is this different from the previous version?  You still have
the same call to sum which requires a contiguous argument list on the stack.

-- 
Andreas Schwab                                  "And now for something
schwab@suse.de                                   completely different."
SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg