Re: Is this tai-recursion?

defn noob <circularfunc@xxxxxxxx> writes:

On 30 Juni, 14:38, p...@xxxxxxxxxxxxxxxxx (Pascal J. Bourguignon)
wrote:
defn noob <circularf...@xxxxxxxx> writes:
is this tail-recursion or iteration?

(define (fib n)
(define (fibs a b n)
(if (<= n 1)
b
(fibs b (+ a b) (- n 1))))
(if (= n 0)
0
(fibs 0 1 n)))

There is no difference between tail-recursion and iteration.
That's why tail-recursion is so simple, compared to normal recursion.

--
__Pascal Bourguignon__


so this is tail-recursion/iteration and not recursion...?


and normal recursion = treerecursion

Matter is condensed energy.

It's the same. At some level of abstraction, there is no difference
between an iteration and a recursion. This is very obvious when all
you have in your function is tail recursion. But even if you have
"tree-recursion", you can easily transform it into an iteration,
using an auxiliary stack.

Note that your processor doesn't do recursion. It has a simple loop:

loop
fetch next instruction from instruction pointer
increment instruction pointer
execute instruction
end

Only when your program has a recursive function call, some
instructions will manipulate the processor stack. It's only a nice
optimization for the processor to provide a stack, and it helps in
handling interrupts, but a processor without an implicit stack works
as well, only the program would manipulate the stack explicitely.
This is done by code generated by the compiler. What happens is that
once we have a processor stack often grows toward the heap, and
therefore may collide with the heap. What's worse, is that since it is
used to handle external events (interrupts), its growth is not
entirely under program control. That's why the OS tries to limit this
growth, and therefore why there are some constraints on the processor
stack. For an explicit stack the only constraint would be that of
free heap memory. Hence the practical considerations about recursion.
Compilers don't do automatic conversion from "tree-recursion" to
iteration (but they could do it), but on the other hand, it's trivial
for them to do the conversion from tail recursion to iteration,
therefore we get automatic equivalence in this case.



So, formally, fibs a tail-recursive function. But all scheme compilers
are mandated to optimize it out and to generate iterative code.
Therefore in practice, it's an iteration.


--
__Pascal Bourguignon__
.

Relevant Pages

  • Re: counting BST nodes using iteration
    ... It uses iteration. ... size_t nodecount(node *root) { ... The problem is how to declare the stack size because we do not know ... converting the above recursion into iteration. ...
    (comp.programming)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)
  • Re: iterative copying of binary expression trees
    ... tail recursion as de facto optimized (bounded stack space). ... "Functional iteration" makes high sense IMHO. ... and an iterative procedure from an iterative process. ...
    (comp.lang.lisp)
  • Re: counting BST nodes using iteration
    ... without using recursion. ... It uses iteration. ... delete stack. ... If you have a decent stack ADT, ...
    (comp.programming)
  • Re: Too much stack usage?
    ... It is likely that the rest of the stack is bogus ... ... The function which the crash occurs in does not do anything specific. ... The big question is: what is the instruction at crash point: 0x0807b1b1? ... In order to understand recursion you must first understand recursion. ...
    (comp.unix.solaris)
Loading