Hi all, I am playing around with latin squares, and wrote a recursive function that searches for valid combinations. Apart from the fact that there are very many, I run into troubles beginning with size 10x10 because the recursion depth becomes too large (max of 10x9-1=89 in this case). Why is this a problem? Isn't there enough space allocated to the stack? Can this be increased? The memory demand shouldn't be terrible, with only minimal local variables (only set and the function params r,c,t - s is local to a block called only once when a solution is found). Even if variables aren't stored efficiently, a recursion depth of 100 shouldn't consume more than a couple of kilobytes. Is this a fundamental misunderstanding of the way R works? Pascal BTW: Is there a way to pass variables "by reference" in function calls? ------ The function stripped-down to the essential looks like this: latin.square <- function(t = 4) { latinCheck <- function(r,c,t) { set <- setdiff(LETTERS[1:t],c(m[r,],m[,c])); for(i in set) { m[r,c] <<- i; if(c<t) { latinCheck(r,c+1,t); } else { if(r<t) { latinCheck(r+1,1,t); } else # found a solution { s <- paste(m[1,],collapse="",sep="");; for(i in 2:t) { s <- paste(c(s,"-",m[i,]),collapse="",sep=""); } cat(s,"\n"); } } } m[r,c] <<- NA; } latinSolutions <<- character(0); fullset <<- LETTERS[1:t]; m <<- matrix(nrow=t,ncol=t); m[1,] <<- LETTERS[1:t]; latinCheck(2,1,t) } l
Perhaps you could take the trouble to read the error message, which is Error in inherits(x, "factor") : evaluation is nested too deeply: infinite recursion? The evaluation depth is controlled by options(expressions=). Increasing it allows your code to run, albeit very slowly. On Tue, 25 Nov 2003, Pascal A. Niklaus wrote:> Hi all, > > I am playing around with latin squares, and wrote a recursive function > that searches for valid combinations. > Apart from the fact that there are very many, I run into troubles > beginning with size 10x10 because the recursion depth becomes too large > (max of 10x9-1=89 in this case). > > Why is this a problem? Isn't there enough space allocated to the stack?It is space for expressions. This is a safety check to avoid infinite recursion overrunning the C-level stack and crashing R (and thereby losing all the current work). There is no portable way to check the C stack size and usage that we know of.> Can this be increased? The memory demand shouldn't be terrible, with > only minimal local variables (only set and the function params r,c,t - s > is local to a block called only once when a solution is found). Even if > variables aren't stored efficiently, a recursion depth of 100 shouldn't > consume more than a couple of kilobytes.Why `shouldn't' it? Have you any idea of the storage requirements of R objects?> Is this a fundamental misunderstanding of the way R works?It is a misreading of a simple message, for sure. [...] -- Brian D. Ripley, ripley at stats.ox.ac.uk Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/ University of Oxford, Tel: +44 1865 272861 (self) 1 South Parks Road, +44 1865 272866 (PA) Oxford OX1 3TG, UK Fax: +44 1865 272595
>>>>> "Pascal" == Pascal A Niklaus <Pascal.Niklaus at unibas.ch> >>>>> on Tue, 25 Nov 2003 16:10:56 +0100 writes:Pascal> Hi all, I am playing around with latin squares, and Pascal> wrote a recursive function that searches for valid Pascal> combinations. Apart from the fact that there are Pascal> very many, I run into troubles beginning with size Pascal> 10x10 because the recursion depth becomes too large Pascal> (max of 10x9-1=89 in this case). Pascal> Why is this a problem? Isn't there enough space Pascal> allocated to the stack? Can this be increased? The Pascal> memory demand shouldn't be terrible, with only Pascal> minimal local variables (only set and the function Pascal> params r,c,t - s is local to a block called only Pascal> once when a solution is found). Even if variables Pascal> aren't stored efficiently, a recursion depth of 100 Pascal> shouldn't consume more than a couple of kilobytes. Pascal> Is this a fundamental misunderstanding of the way R Pascal> works? a slight one, at least: The recursion depth is limited by options(expressions = ...), i.e. getOption("expressions") which is 500 by default. We've had similar problem when drawing a somewhat large dendrogram (of less than 10000 end nodes still). I think we should consider increasing the *default* maximal recursion depth (from 500 to a few thousands) and even think about increasing the maximally allowed value for 'expressions' (which is 100000). Martin