Recursion

[SBM Productions]

I managed to program A* as well... I was very proud......still am.
I'm trying to think of a method to do A* in 3D using convex hulls as nodes........Evilish stuff

[SBM Productions]

The results were this:
Freebasic stack count reached 23741 before error.
QB4.5 stack count reached 102 before error.

This was in a way a waste of time, but I have time to waste....here's the code I used

Code:

declare sub stackkiller (x1, y1)
dim shared stackcount as integer

stackkiller x1,y1
sub stackkiller(x1,y1)
x1=x1+1
y1=y1+1

stackcount = stackcount + 1
locate 1,1:print "This has been called "+str$(stackcount)+" times"
sleep
stackkiller x1,y1
end sub

I put in the x and y to simulate a sub that does something.....

[na_th_an]

It doesn't matter if the SUB does much or little. What takes stack space is:

1.- The parameters passed, which are pushed into the stack before calling.
2.- The return address, pushed into the stack as well
3.- Local variables inside the SUB: these are reserved in the stack.

[helium]

Does FB do some tail-recursion-optimisation? I'm not at home, so I can't test on my own.


For those, who don't knwo tail-recursion:

A tail-recursive call is a call to the function without doing anything to the result:
e.g.

Sub foo (n as integer)
Print n
If n >= 0 Then
foo n - 1 ' tail recursive call
End If
End Function

But

Function fac (n as integer)
If x <= 1 Then
fac = 1
Else
fac = n * fac(n-1) ' none tail recursive call
End If
End Function


tail-recursive calls can be optimized: Instead of calling the function iteself you assign new values to the parameters and do some kind of goto to the start of the function.

(gcc 4 will even be able to convert some none-tail-recursion into tail-recursion doing the accumulator-trick :o but that's another topic)

[na_th_an]

tail-recursive calls can be optimized: Instead of calling the function iteself you assign new values to the parameters and do some kind of goto to the start of the function.

That's the recursive to iterative transformation algorithm. It's relatively easy to do on paper, but it would mean some nasty operations with the abstract syntax tree in the code generator. I dunno if FB does it, but according to v1ctor this ain't a "optimizing compiler".