Page 1 of 1
Step through a recursive handler
Posted: Tue Jun 14, 2016 8:29 pm
by dunbarx
This is computer science 101. If you have:
Code: Select all
on mouseUp
answer factorial(5)
end mouseUp
function factorial var
if var = 0 then return 1
else return var * factorial(var - 1)
end factorial
You get 120. But if one steps through the function handler, where do the intermediate results get stored? In other words, how do it know? I get how the recursion works, but I do not get how (or rather, where) LC keeps track of the accumulating intermediate values.
Craig Newman
Re: Step through a recursive handler
Posted: Wed Jun 15, 2016 3:32 pm
by jacque
I believe each reiteration keeps its own copy of the parameter variable, and each copy stays in RAM until the entire recursion is complete. That's why too much recursion can fill up all available memory and cause a crash.
Re: Step through a recursive handler
Posted: Wed Jun 15, 2016 6:36 pm
by dunbarx
Jacque.
The variable "var" in my example counts down as each recursive "loop" proceeds. There is no explicit line of code that decrements that variable, it just does. No changes at all are seen in the debugger.
Are you saying that LC creates a new internal invisible variable where it stores the intermediate values of the process? And that variable cannot be seen at all? I have never heard of such a thing. Is this a recursion-special case? And is the decrementing variable "var" somehow also managed by the recursive "loop"? How do it know?
How do it know?
Craig
Re: Step through a recursive handler
Posted: Wed Jun 15, 2016 7:09 pm
by mwieder
Craig-
The 'var' parameter that gets passed to the function will be different each time through the recursion. As it unwinds, the var variable gets updated with a new value.
Re: Step through a recursive handler
Posted: Wed Jun 15, 2016 8:05 pm
by dunbarx
Mark.
I could easily write a factorial function that does not use recursion at all. It would be longer, but I am not sure that much slower. In any case, I am still perplexed at where LC is maintaining the intermediate value, building it as it loops. Does it have a name? Is it unique to recursion gadgetry? And one more time, how does LC "know" that a recursive loop is running at all, and how does it distinguish this type of process from any other?
Craig
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 2:00 am
by mwieder
Craig-
There *is* an explicit line of code that sets the var variable. It's the parameter to the function.
You are first calling it with var = 5. Think of it this way (unwinding the recursion and substituting for var)
Code: Select all
function factorial 5
if 5 = 0 then return 1
else return 5 * factorial(5 - 1)
end factorial
at that last line of code in the function you're calling a new instance of the factorial function this way:
Code: Select all
function factorial 4
if 4 = 0 then return 1
else return 4 * factorial(4 - 1)
end factorial
then you're calling it again like
Code: Select all
function factorial 3
if 3 = 0 then return 1
else return 3 * factorial(3 - 1)
end factorial
etc.
on the way out the functions return
1 (the innermost recursion)
2 * factorial(2-1) -- the next level out
3 * factorial(3-1) -- and so on
Each time the factorial function gets invoked in the recursion it gets a new ecosystem of local variables (well, in this case there's only one) and that includes the parameter that's being passed. So there's no hidden variable that the engine is keeping from you.
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 2:32 am
by jacque
Good explanation, Mark.
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 5:29 am
by dunbarx
I really do understand the decrementing of the "var" variable. I am sorry I even mentioned it.
My last handful of rants have focussed on the intermediate accumulator of successive results of the recursive loop itself. I am intrigued by how LC stores the running sums.
Obviously it does, somewhere. But where?
Craig
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 8:46 am
by Thierry
dunbarx wrote:I am intrigued by how LC stores the running sums.
Obviously it does, somewhere. But where?
Hi Craig,
Check this script which is basically the same as yours but
with some intermediate variable settings to follow the process.
Mmm, well hope so
Code: Select all
local tmp
local _increment
on mouseUp
put empty into tmp
put empty into _increment
answer factorial( 5)
put tmp
end mouseUp
function factorial var
local _return, _step
add 1 to _increment
put _increment into _step
if var = 1 then
put 1 into _return
followReturns _increment, _step, _return
return _return
else
followReturns _increment, _step, _return
put var * factorial(var - 1) into _return
followReturns _increment, _step, _return
return _return
end if
end factorial
on followReturns i, s, r
put "increment: " & i & " step: " & s & " returns: " & r & cr after tmp
end followReturns
HTH,
Thierry
PS: I changed the value for the test: var = 1 instead of 0
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 2:15 pm
by dunbarx
Thierry.
I see how you have deconstructed and annotated (quite nicely) the recursion process. But YOU did that.
How does LC do that? Obviously, somehow. Inside and invisible, eh? Well, OK.
But I still am intrigued by how it knows to do that, since there is nothing "typing" a recursion handler as opposed to any other kind of handler. Does that make my quandary more clear?
Or am I making a lot of noise over nothing?
Craig
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 2:33 pm
by Thierry
dunbarx wrote:Thierry.
I see how you have deconstructed and annotated (quite nicely) the recursion process. But YOU did that.
How does LC do that? Obviously, somehow. Inside and invisible, eh? Well, OK.
But I still am intrigued by how it knows to do that, since there is nothing "typing" a recursion handler as opposed to any other kind of handler. Does that make my quandary more clear?
Craig,
a recursive handler has the same properties as a 'normal' handler; nothing more.
I"m not sure this will make you happy, but here is a link which might give you some insights:
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack".
Check for details:
https://en.wikipedia.org/wiki/Call_stack
HTH,
Thierry
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 4:30 pm
by jacque
Craig, I think the piece you're missing is that the engine does what Thierry did. Each iteration behaves as though it's a new call to the handler. The engine creates a new instance of the variable in memory for that iteration. In this case there would be several instances of the "var' variable, each with a different value. The engine keeps track of which instance belongs to each iteration.
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 6:01 pm
by mwieder
Craig-
Also, the reason I used explicit numbers and avoided using the 'var' variable in my expanded example is to avoid confusion. When you recurse through the factorial function, you can think of this as several copies of the function being created on the fly, each with its own set of local variables. If we had proper tail recursion we could avoid a lot of copying by the engine, but right now that's the way it works.
So while there's no hidden local variable being created, actually a copy of the whole function is being created so that there's no conflict.
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 7:13 pm
by dunbarx
All.
Thanks, got it. It could not have been otherwise, I suppose.
I was interested in seeing if there was some native attribute within LC that I simply was not aware of. The last time that happened, was with the (and I cannot remember the exact name anymore, it seems) the "messagesMessage" (sic?)
I think it was Richard who told me about this, in response to a long lost thread.
Craig
Re: Step through a recursive handler
Posted: Thu Jun 16, 2016 10:03 pm
by mwieder
Craig-
Oh, there are a lot of those.
The messageMessages is certainly one of them. Most you don't need to bother with, or they are of limited use.
The debugger uses several undocumented global properties: the traceStack, the traceReturn, the traceAbort, etc.
There are also several undocumented global variables the engine uses: gRevDevelopment is one I use frequently.