Re: Recursion Optimization

[Kevin Atkinson <kevinatk at home dot com>]

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.

> |> 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.  

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);
}