무한 재귀 이해 및 회피 R

Question

R에서 무한 재귀를 처리하는 방법에 대한 조언을 찾을 수 없습니다. 다른 사람들이 이점을 누릴 수 있도록 가장 일반적인 방법으로 문제를 설명하고 싶습니다. 자유롭게 편집하십시오.

나는 루프

이 잘 실행되고

for (k in 1:n){ for (i in 1:m){ 
f[i,,k] <- an expression that depends on g[i-1,,k] 
g[i,,k] <- a mixture of g[i-1,,k] and f[i,,k]}} 

double를 실행하는 데 사용하지만, 지금은 최고의 내 기준에 맞는 것이 K를 찾기 위해 희망했다. 그래서 함수를 나중에 최적화하거나 unilot 할 수 있도록하기로했습니다. 나는 다음과 같이 썼습니다.

두 문제가 비슷하다고 생각했지만 큰 놀라움에 따라 무한 재귀 오류가 발생했습니다.

나는 최대 메모리에 대해서 읽었지 만, 그것을하기위한 더 심미적 인 방법이 있다고 확신한다.

내 재현 예 : dailyreturn가 (길이 2080) 벡터

A는 1414 X 24 행렬

나는 희망이 도움을이다

library(memoise) 

gradient <- function(x,y,tau){if (x-y > 0) {- tau} else {(1-tau)}} 
aj <- c(-3,-4,-2,-3,-5,-6,-4,-5,-1,rep(-1,15)) 
f <- function(x,vec){sum(x^vec)-1} 
root <- uniroot(f, interval=c(0,200), vec=aj)$root 

memloss<-function(i,k){if (i==1) {c(rep(0,24))} else if (i <= 0 | k < -5) {0} else {gradient(dailyreturn[i-1],weight(i-1,k)%*%A[i-1,],0.0025)*A[i-1,]}} 
memweight <- function(i,k){if (i==1) {c(rep(root,24)^aj)} else if (i <= 0 | k < -5) {0} else {(exp(- (2^(k)/(sqrt(1415))) * loss(i,k)))/(weight(i-1,k) %*% exp(- 2^(k)/(sqrt(1415)) * loss(i,k))) * weight(i-1,k)}} 
loss <- memoize(memloss) 
weight <- memoize(memweight) 

.

Answer 1

세 가지 문제가 있습니다.

먼저 재귀를위한 초기 사례가 필요합니다. 다음은 무한 재귀를 유도합니다 (i의 값은 계속 감소하지만 결코 멈추지 않습니다).

f <- function(i) g(i-1) 
g <- function(i) g(i-1) + f(i) 
f(5) 

다음과 같습니다.

f <- function(i) g(i-1) 
g <- function(i) if(i <= 0) 0 else g(i-1) + f(i) 
f(5) 

두 번째 문제점은 이러한 값 중 일부가 지수 적 횟수로 다시 계산된다는 것입니다.

f(500) # Too long 

더 추상화 관점에서 에지 함수 호출에 대응 i, 의 모든 값에 대한 꼭지점과 f(i)g(i)이 그래프를 고려한다. 재귀를 사용하면이 그래프를 마치 나무처럼 탐색 할 수 있습니다. 그러나이 경우에는 트리가 아니므로 동일한 기능을 (동일한 노드를 탐색하는) 매우 많은 횟수로 평가하게됩니다. 다음 코드는이 그래프를 그립니다.

library(igraph) 
n <- 5 
g <- graph.empty() 
g <- g + vertices(paste0("f(", 1:n, ")")) 
g <- g + vertices(paste0("g(", 0:n, ")")) 
for(i in 1:n) { 
    g <- g + edge(paste0("f(", i ,")"), paste0("g(", i-1, ")")) 
    g <- g + edge(paste0("g(", i ,")"), paste0("f(", i, ")")) 
    g <- g + edge(paste0("g(", i ,")"), paste0("g(", i-1, ")")) 
} 
plot(g) 

한 가지 해결 방법은 당신이 이미 그들을 다시 계산 피하기 위해 계산 한 값을 저장하는 것입니다 이 memoization라고합니다. 이 기능을 memoise 때

library(memoise) 
f <- function(i) G(i-1) 
g <- function(i) if(i <= 0) 1 else G(i-1) + F(i) 
F <- memoize(f) 
G <- memoize(g) 
f(500) 

은 재귀 호출의 수는 선형, 하게하지만 여전히 너무 클 수 있습니다.초기 오류 메시지에 의해 제안 당신이 한계를 증가시킬 수있다 :이 충분하지 않은 경우

options(expressions = 5e5) 

, 당신은 i의 점점 더 큰 값을 사용하여 테이블을 미리 채울 수 있습니다. 귀하의 예제와 :

options(expressions = 5e5) 
loss(1000,10) # Does not work: Error: protect(): protection stack overflow 
loss(500,10) # Automatically stores the values of loss(i,100) for i=1:500 
loss(1000,10) # Works 

셋째, 기능이 불필요하게 호출 스택의 크기를 증가 시킨다는 호출이있을 수 있습니다. 예를 들어, 오류 후 traceback()을 입력하면 함수 인수 내에서 weight(i,k) 및 loss(i,k)이 사용되므로 많은 중간 함수 이 호출 스택에 있음을 알 수 있습니다. 함수 인수 밖에서 이러한 호출을 이동하면 호출 스택이 작아지고 작동하는 것처럼 보입니다.

library(memoise) 
gradient <- function(x,y,tau){ 
    if (x-y > 0) { - tau } 
    else   { (1-tau) } 
} 
aj <- c(-3,-4,-2,-3,-5,-6,-4,-5,-1,rep(-1,15)) 
f <- function(x,vec){sum(x^vec)-1} 
root <- uniroot(f, interval=c(0,200), vec=aj)$root 
memloss<-function(i,k){ 
    cat("loss(", i, ",", k, ")\n", sep="") 
    if (i==1) { 
    c(rep(0,24)) 
    } else if (i <= 0 | k < -5) { 
    0 
    } else { 
    w <- weight(i-1,k) # Changed 
    gradient(dailyreturn[i-1],w%*%A[i-1,],0.0025)*A[i-1,] 
    } 
} 
memweight <- function(i,k){ 
    cat("weight(", i, ",", k, ")\n", sep="") 
    if (i==1) { 
    c(rep(root,24)^aj) 
    } else if (i <= 0 | k < -5) { 
    0 
    } else { 
    w <- weight(i-1,k) # Changed 
    l <- loss(i,k)  # Changed 
    (exp(- (2^(k)/(sqrt(1415))) * l))/(w %*% exp(- 2^(k)/(sqrt(1415)) * l)) * w 
    } 
} 
loss <- memoize(memloss) 
weight <- memoize(memweight) 

A <- matrix(1, 1414, 24) 
dailyreturn <- rep(1,2080) 
options(expressions = 1e5) 
loss(1400,10)