MATLAB은 꼬리 호출 최적화를 수행합니까?

Question

나는 최근에 하스켈을 배웠고 가능할 때 순수한 함수 스타일을 다른 코드로 옮기기 위해 노력하고있다. 이것의 중요한 측면은 모든 변수를 불변 (immutable) 즉 상수로 취급하는 것입니다. 그렇게하기 위해서 명령형으로 루프를 사용하여 구현되는 많은 계산은 재귀를 사용하여 수행되어야하는데, 일반적으로 각 함수 호출에 대해 새로운 스택 프레임을 할당하기 때문에 메모리 페널티가 발생합니다. 그러나 테일 호출 (호출 된 함수의 반환 값이 호출 수신자에게 즉시 반환되는)의 특수한 경우에는 테일 호출 최적화라는 프로세스로이 페널티를 무시할 수 있습니다 (한 가지 방법으로 기본적으로 스택을 올바르게 설정 한 후 호출을 jmp로 대체). MATLAB은 기본적으로 TCO를 수행합니까, 아니면 TCO를 알려줄 수 있습니까?

Answer 1

나는 간단한 꼬리 재귀 함수를 정의하는 경우 :

function tailtest(n) 
    if n==0; feature memstats; return; end 
    tailtest(n-1); 
end 

을하고 매우 깊은 재귀 있도록 전화 :

set(0,'RecursionLimit',10000); 
tailtest(1000); 

을 그것은 스택 프레임이있는 것처럼 보이지 않는다 많은 기억을 먹는다. 내가 할 경우, 훨씬 더 깊은 재귀 :

set(0,'RecursionLimit',10000); 
tailtest(5000); 

다음 (내 컴퓨터, 오늘) MATLAB은 단순히 충돌

: 프로세스가 무례하게 죽는다.

나는 이것이 TCO를 수행하는 MATLAB과 일치하지 않는다고 생각합니다. 함수가 단일 인수가 아닌 로컬 변수가없는 한 곳에서만 함수를 꼬리로 호출하는 경우는 누구나 기대할 수있는만큼 간단합니다.

So : 아니요, MATLAB은 적어도 기본적으로 TCO를 전혀 수행하지 않는 것으로 보입니다. 나는 (지금까지) 그것을 가능하게 할지도 모른 선택권을 찾지 않았다. 어떤 것이 있으면 나는 놀랄 것이다.

스택을 날려 버리지 않는 경우 재귀 비용은 얼마입니까? Bill Cheatham의 답변에 대한 제 의견을 읽어보십시오. 시간 오버 헤드는별로 중요하지 않지만 미친 것은 아닙니다.

... Bill Cheatham이 내가이 코멘트를 남긴 후에 그의 대답을 삭제했다는 것을 제외하고. 승인. 그래서 피보나치 함수와 간단한 tail-recursive 함수를 반복적으로 구현하고 두 가지 모두에서 본질적으로 동일한 계산을 수행했으며 두 경우 모두 fib(60)에서 시간을 측정했습니다. 재귀 구현은 반복 실행보다 실행 시간이 약 2.5 배 길다. 물론 상대 오버 헤드는 반복 당 하나의 덧셈과 하나의 뺄셈보다 많은 일을하는 함수에서 더 작을 것입니다.

(나는 또한 delnan의 정서에 동의합니다. 하스켈에서 자연의 느낌 종류의 높은 재귀 코드는 MATLAB에서 unidiomatic 것으로 일반적으로 가능성이) 단지 그것의 지옥에 대한 반복을 피하기