다음은 큰 'n'에 대한 스택 오버플로가 발생하며 이유를 이해할 수 있습니다.이 코드로 인해 스택 오버플로가 발생하는 이유는 무엇입니까?
def factorial(n)
(n > 1) ? (return (n * factorial(n - 1))) : (return 1)
end
왜 다음과 같은 원인으로 오버플로가 발생합니까?
def factorial(n, k)
(n > 1) ? (return factorial(n - 1, lambda {|v| return k.call(v * n)})) : (return k.call(1))
end
두 번째 알고리즘은 각각 이전 절차에 대한 참조를 포함하는 람다 프로 시저 체인 n을 생성합니다. 루비가 정확히 무엇을하는지는 모르지만, 꼬리 재귀 적 언어에서는 덤프의 k.call도 꼬리 위치에 있기 때문에 스택이 두 번째 알고리즘에서 오버 플로우하지 않습니다. Brian의 실험에서 알 수 있듯이 Ruby에 적절한 테일 호출이없는 경우, 빗대 어를 호출 할 수있을 정도로 똑똑하지만 체인의 헤드가 호출 될 때 람다에 대한 중첩 호출의긴 체인이 오버플로됩니다. -recursive factorial 루프로 호출 (= 꼬리 호출 최적화).
두 번째 버전은 계승에서 계속 반복됩니다. 나는 루비가 TCO를하지 않았다고 생각했다. 그러나 그것은 람다에 도달 할 때까지 스택을 날려 버리지 않습니다. 나는 혼란스러워. (다른 사람들은 훨씬 더 혼란 스럽거나 질문을 읽지 않았다. 나는 적절하게 다른 사람들에게 downvoting을하고있다.) –
"하지만 람다에 도착할 때까지는 그걸 쏘지 않는다." - 응? 나는 이해하지 못한다. –
두 번째 예제가 여전히'factorial'에서 반복되는 것을 감안할 때, 나는'k.call (1)'의 기본 경우에 도달하기 전에 스택을 오버플로 할 것으로 예상했습니다. 그러나 위의 두 번째 예제 코드에서'계승 (factorial) '호출은 첫 번째 예제와 다른 동작 인 스택 (매우 큰 n의 경우에도)을 오버플로하지 않습니다. 두 번째 예제는 그 기본 케이스에 도달하고 많은'k.call '이 발생할 때까지 오버플로하지 않습니다. TCO가 없으면 어떻게 그렇게 크게 나아갈 지 알 수 없습니다. –
첫 번째 함수에서와 마찬가지로 재귀 호출은 시스템이 처리하기에는 너무 많아 질 수 있습니다.
대부분의 언어에서 함수 호출은호출 스택으로 이동합니다.이 호출 스택은 실제로는 스택입니다. 함수를 재귀 적으로 호출하면 호출 스택에 계속 추가됩니다. 결국 스택을 채우면 스택 오버 플로우가 발생합니다. 재귀 수준이 깊어지는 재귀 함수를 실행할 때 항상 위험합니다.
-1 : cf. "다음은 큰 'n'에 대해 오버플로가 발생하며 이유는 무엇인지 이해할 수 있습니다. –
첫 번째 스택 오버플로가 발생합니다 ... 호출 스택이 너무 커집니다.
오버플로? 또는 StackOverflow ?! –
-1, 사용자의 소지가 있습니다. –