[R] understanding recursive functions

[Wacek Kusnierczyk]

Jeffrey Horner wrote:
> joseph.g.boyer at gsk.com wrote on 12/18/2008 04:22 PM:
>> I'm trying to understand the use of recursive functions described on
>> page 45 of An Introduction to R by the R core development team.
>>
>> A function is a list of expressions, which all get executed with only
>> the last being assigned to a global variable, right? So if a function
>> refers recursively to itself, it should simply start with the first
>> expression and go from there. At least that is my understanding of
>> why the example given on page 45 works.
>>
>> In light of the above, I would appreciate it if someone would
>> understand why the following example does not work:
>>
>> q <- function(x,h) {if (x < 2) {x <<- x+1; return(q(x))} else return(x)}
>>
>> If x < 1, this should add 1 to x and go back to the beginning of the
>> if expression, and the final result should be 2. So q(0) should
>> return 2. But
>> it returns an error message.
>
> All references to x save one (the assignment with the <<- operator)
> are found within the current frame, not by lexical scoping, and hence
> is never changed...

i'd say all references in the code above are looked up by lexical
scoping.  the catch is that the assignment operator <<- specifies that
the assignment should be made not to a local variable (in the current
environment), but to the appropriately named variable in the nearest
enclosing environment, starting with the direct parent, ending with the
global environment. 

the closure environment of the function is the global environment, and
this is the parent environment for the environment within a call to q. 
the assigned-to x is always looked up first in the parent (thus, global)
environment, and that's where the assignment is made.  all other
occurrences of the identifier 'x' are looked up starting from the call
environment, and they are bound there, since x is a parameter of q.  q
calls itself with the same value it receives, first assigning to the
global x, but with little sense, since it always assigns the same value.

it's a pity that <<- is not explained in ?`<<-` clearly enough:

"  The operators '<<-' and '->>' cause a search to made through the
     environment for an existing definition of the variable being
     assigned.  If such a variable is found (and its binding is not
     locked) then its value is redefined, otherwise assignment takes
     place in the global environment.  Note that their semantics differ
     from that in the S language, but are useful in conjunction with
     the scoping rules of R.  See 'The R Language Definition' manual
     for further details and examples."

the search is made through the environment, but *starting at the parent*
(and this means the lexical parent as in parent.env, not the dynamic
parent as in parent.frame):

x = 0
foo = function(x) { x <<- 1; x }
foo(2)
# 2, not 1
x
# 1, not 0

clearly, in a call to foo x is found in the call environment, but is not
assigned there.


vQ