Skip to content

understanding recursive functions

10 messages · joseph.g.boyer at gsk.com, Jeffrey Horner, (Ted Harding) +3 more

Jeffrey Horner
# 
joseph.g.boyer at gsk.com wrote on 12/18/2008 04:22 PM:
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... producing infinite recursion. The following at least 
fixes your example:

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... producing infinite recursion. The following at least 
fixes your example:

q <- function(x,h) {if (x < 2) {x <<- x+1; x <- x+1; return(q(x))} else 
return(x)}
ls() # no x in global env just yet
q(-10)
ls()


Jeff

  
    
  


  


      

    

    

      
      

        


  

        

      (Ted Harding)
    

    

      
      #
    

  


  

      
On 18-Dec-08 22:33:28, Jeffrey Horner wrote:

            

      
      
      
    

        
The following fixes it even more simply (using the same principles):

  q <- function(x,h){
    if (x < 2) {u <- x+1; return(q(u))} else return(x)
  }

Note that "<<-" is not necessary.

Just to test the method more thoroughly:

  q <- function(x,h){
    if (x < 2) {u <- x+h; return(q(u,h))} else return(x)
  }

  q(0,0.3)
# [1] 2.1

Ted.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at manchester.ac.uk>
Fax-to-email: +44 (0)870 094 0861
Date: 18-Dec-08                                       Time: 22:51:41
------------------------------ XFMail ------------------------------

  
  


  


      

    

    

      
      

        


  

        

      Wacek Kusnierczyk
    

    

      
      #
    

  


  

      
Jeffrey Horner wrote:

            

      
      
      
    

        
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

  
  


  


      

    

    

      
      

        


  

        

      Wacek Kusnierczyk
    

    

      
      #
    

  


  

      
Wacek Kusnierczyk wrote:

            

      
      
      
    

        
the description is further imprecise as to what happens if such a
variable is found but is locked:

foo = function() {
   x = 0
   lockBinding("x", environment())
   (function() x <<- 1)()
   unlockBinding("x", environment())
}

foo()
# error

if analysed logically (IF (found AND not locked THEN assign) ELSE assign
globally), the description is wrong. 

vQ

  
  


  


      

    

    

      
      

        


  

        

      Peter Dalgaard
    

    

      
      #
    

  


  

      
Wacek Kusnierczyk wrote:

            

      
      
      
    

        
Yes.

If such a variable is found  then its value is redefined (unless its 
binding is locked), otherwise assignment take place in the global 
environment.

  
    

      
      
    

  


  


      

    

    

      
      

        


  

        

      Wacek Kusnierczyk
    

    

      
      #
    

  


  

      
Peter Dalgaard wrote:

            

      
      
      
    

        
it might help the help to be have the help say that if the variable is
found but locked then an error is raised.

vQ

  
  


  


      

    

    

      
      

        


  

        

      Nordlund, Dan (DSHS/RDA)
    

    

      
      #
    

  


  

          

      
      
      
    

        
I am by no means an expert in programming so I will defer to the experts. But assuming the OP was not intentionally trying to assign in a parent environment, couldn't the above function be written as

q <- function(x,h){if (x < 2) q(x+h,h) else return(x)

Hope this is helpful,

Dan

Daniel J. Nordlund
Washington State Department of Social and Health Services
Planning, Performance, and Accountability
Research and Data Analysis Division
Olympia, WA  98504-5204

  
  


  


      

    

    

      
      

        


  

        

      Nordlund, Dan (DSHS/RDA)
    

    

      
      #
    

  


  

          

      
      
      
    

        
Sorry, I forgot the final '}' .  Or I think you can eliminate the leading '{' and final '}' in this case.

 q <- function(x,h) {if (x < 2) q(x+h,h) else return(x)}