Step through a recursive handler

[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

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

[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

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

[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

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

[jacque]

Good explanation, Mark.

[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

[Thierry]

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

[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

[Thierry]

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

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

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

[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

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