Infinite loop detection in recursive function (R)
I have a df test:
testdf<-data.frame(x = seq(1,10), y= c(1, 1, 4, 3, 2, 6, 7, 4, 9, 10))
testdf
x y
1 1 1
2 2 1
3 3 4
4 4 3
5 5 2
6 6 6
7 7 7
8 8 4
9 9 9
10 10 10
I want to write a function that enters a row number and "follows" the y value until it finds a row for which column x = column y.
get_acc_x<-function(rownum){
if(testdf[rownum, 'x'] == testdf[rownum, 'y']){
return(rownum)
}else{
get_acc_x(testdf[rownum, 'y'])
}
}
So running get_acc_x (1) returns 1, get_acc_x (9) returns 9, get_acc_x (2) returns 1, get_acc_x (5) also returns 1, etc.
But, if I were to run this function on the 8th, it would end up in an infinite loop, moving back and forth between 3 and 4. What is the easiest way to detect an infinite loop in this situation? I want to keep track of past inputs, so I can stop the function if the same input is used more than once, but I don't know the best way to track inputs.
source to share
You can pass a parameter to mark the visited lines:
get_acc_x<-function(rownum, seen){
if (seen[rownum]) {
# Whatever you want to do, cycle detected
}
seen[rownum] <- T
if(testdf[rownum, 'x'] == testdf[rownum, 'y']){
return(rownum)
}else{
get_acc_x(testdf[rownum, 'y'], seen)
}
}
When called, use get_acc_x(rownum, rep(F, nrow(df))
to pass the entire parameter False
.
source to share
If you don't want to explicitly skip the visited nodes, you can read them from the call stack using sys.frames
. If you think the recursion is going to be small enough, there shouldn't be too many performance hitches, and since it doesn't change the signature, you shouldn't have to change any calling code.
get_acc_x2<-function(rownum){
if(testdf[rownum, 'x'] == testdf[rownum, 'y']){
return(rownum)
}else{
rownum %in% sapply(head(sys.frames(), -1), `[[`, "rownum") &&
stop('infinite recursion detected')
get_acc_x2(testdf[rownum, 'y'])
}
}
Example:
> get_acc_x2(8)
Error in get_acc_x2(8) : infinite recursion detected
source to share
You need to pass the previously seen values as an argument. I added a wrapper function that processes the original empty vector.
x <- c(1,2,3,4,5,6,7,8,9,10)
y <- c(1,1,4,3,2,6,7,4,9,10)
df <- data.frame(x,y)
get_acc_x <- function(rownum,df) get_acc_x_rec(rownum,df,numeric())
get_acc_x_rec<-function(rownum,df,prev){
if(df[rownum, 'x'] == df[rownum, 'y']){
return(rownum)
}else{
if(is.element(df[rownum, 'y'],prev)) get_acc_x(df[rownum, 'y'],df,c(prev,rownum))
else stop("Damnit!")
}
}
source to share