Обнаружение бесконечный цикл в рекурсивной функции (R)

Question

У меня есть тест-ДФ:

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 

Я хочу написать функцию, которая вводит номер строки и «следует» значение у до тех пор, пока не найдет строку для которого столбец 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. Каков самый простой способ обнаружить бесконечный цикл в этой ситуации? Я хочу отслеживать прошлые входы, поэтому я могу остановить функцию, если один и тот же ввод используется несколько раз, но я не знаю, как лучше всего отслеживать входные данные.

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 парах.

Answer 2

Вам необходимо передать ранее увиденные значения в качестве аргумента. Я добавил функцию-обертку, которая обрабатывает начальный пустой вектор.

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

Answer 3

Если вы не хотите, чтобы пройти вдоль посещенных узлов в явном виде, вы можете читать их из стека вызовов с помощью 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