在递归函数中检测无限循环 (R)

Question

我有一个测试数据框 df：

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

我想编写一个函数，输入一行数，然后“跟随”y值，直到找到一个列x等于列y的行。

get_acc_x<-function(rownum){
  if(testdf[rownum, 'x'] == testdf[rownum, 'y']){
    return(rownum)
  }else{
    get_acc_x(testdf[rownum, 'y'])
  }
} 

因此，运行 get_acc_x(1) 返回 1，get_acc_x(9) 返回 9，get_acc_x(2) 返回 1，get_acc_x(5) 也返回 1，以此类推。

但是，如果我对数字 8 运行此函数，它将陷入无限循环，来回在 3 和 4 之间。如何最容易地检测出这种情况下的无限循环？我想跟踪过去的输入，以便在使用相同的输入超过一次时停止函数，但我不知道如何最好地跟踪输入。

- C_Z_

Answer 1

您可以传递一个参数来标记已访问的行：

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)
  }
} 

打电话时，使用get_acc_x(rownum, rep(F, nrow(df))来传递所有False参数。

- zw324

Answer 2

如果您不想显式传递已访问的节点，可以使用 sys.frames 从调用堆栈中读取它们。如果您认为递归深度将相对较浅，则性能不会受到太大影响，并且由于它不改变签名，因此您不必修改任何调用代码。

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'])
  }
} 

例子：

> get_acc_x2(8)
Error in get_acc_x2(8) : infinite recursion detected

- Neal Fultz

Answer 3

您需要将先前看到的值作为参数传递。我添加了一个包装函数来处理传递初始空向量。

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!")
 }
}

- jrdnmdhl