Recursive calls and stack

[Gabriel Genellina]

En Thu, 15 Feb 2007 16:35:25 -0300, Neil Cerutti <horpner at yahoo.com>  
escribió:

> On 2007-02-15, Gabriel Genellina <gagsl-py at yahoo.com.ar> wrote:
>> En Thu, 15 Feb 2007 13:37:19 -0300, Neil Cerutti <horpner at yahoo.com>
>> escribió:
>>
>>> On 2007-02-15, Gabriel Genellina <gagsl-py at yahoo.com.ar> wrote:
>>>> En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti <horpner at yahoo.com>
>>>> escribió:
>>>>> So the effect is that mutual recursion isn't actually any
>>>>> harder.
>>>>
>>>> But some kind of language support is required in this case. At
>>>> least I  don't know how to handle mutual recursion (apart from
>>>> inlining one  function inside the other...). But I'm certainly
>>>> not a "program  transformation guru" (neither a novice!) so I
>>>> would not be surprised if  someone says it can be done...
>>>
>>> What happens (using the model of an imaginary virtual machine,
>>> perhaps like the Python interpreter) is the following.
>>>
>>> A normal function call pushes a call-frame onto a stack. The
>>> call-frame contains information necessary for returning from the
>>> function, and usually a place to store its local variables and
>>> parameters.
>>>
>>> A function called in "tail" position simply overwrites the
>>> current call-frame with the new one instead of pushing it onto
>>> the stack.
>>
>> This is the "kind of language support" menctioned. For tail
>> recursion you  don't require that support.
>
> I'm not sure what you mean. The above support is enough for tail
> recursion, mutual recursion, and any other tail call to be
> "optimized."

I only want to say that tail *recursion* can be eliminated trivially  
transforming the code into a while loop, and that can be done by the  
programmer, and doesn't require compiler support. Head *recursion* can be  
eliminated too by using some storage as temporary stack, and that doesn't  
require external support either. Mutual recursion (and generic tail call  
elimination) require some sort of external support: one can't eliminate  
the call just by transforming the program.

-- 
Gabriel Genellina