js 꼬리 재귀 최적화 코드 공유

小云云원래의: 2018-03-15 15:52:021837검색

데이터 구조와 알고리즘을 배울 때 우리 모두는 모든 재귀가 스택 + 루프로 최적화될 수 있다는 것을 알고 있습니다. 특정 재귀 함수의 경우 일반적으로 수동으로 최적화합니다.

스칼라를 배우면서 꼬리 재귀라는 개념을 접하게 되었습니다. 재귀를 꼬리 재귀로 작성하는 한 컴파일러는 자동으로 최적화를 도와줍니다.
ps: 모든 재귀를 꼬리 재귀로 다시 작성할 수 있는 것은 아닙니다.
js에서 꼬리 재귀는 일반적으로 인터프리터에 의해 최적화됩니다. 그러나 모든 JavaScript 인터프리터가 꼬리 재귀 최적화를 지원하는 것은 아닙니다.
꼬리 재귀 최적화를 지원하지 않는 환경의 경우 재귀를 스택 + 루프로 수동으로 최적화해야 합니다.
여기에서는 꼬리 재귀를 스택 + 루프로 최적화하기 위해 일반적인 방법이 구현되었습니다.
코드는 Ruan Yifeng의 책 "ECMAScript 소개"에서 발췌했습니다.
구체적인 코드는 다음과 같습니다

<span style="font-family: 微软雅黑, "Microsoft YaHei";">function tco(f) {<br/>    var value;    var active = false;    var accumulated = [];    return function accumulator() {<br/>        accumulated.push(arguments);        if(!active) {<br/>            active = true;            while(accumulated.length) {<br/>                value = f.apply(this, accumulated.shift());<br/>            }<br/>            active = false;            return value;<br/>        }<br/>    };<br/>}var sum = tco(function(x, y) {<br/>    if(y > 0) {        return sum(x + 1, y - 1);<br/>    } else {        return x;<br/>    }<br/>});let res = sum(1, 5)<br/>console.info(res);<br/></span>

이 코드는 매우 미묘합니다!

분석
모든 재귀는 루프 + 스택으로 작성될 수 있는 것으로 알려져 있습니다.
각 꼬리 재귀 함수에 대한 구현 버전을 작성하지 않고 모든 꼬리 재귀를 루프 + 스택 실행으로 변환하는 아이디어를 구현합니다.
어려움은 꼬리 재귀적이고 일반적인 구현에 있습니다. 특정 재귀 함수를 타겟팅하는 대신.
요점:

스택에 저장된 데이터는 바로 재귀 함수의 매개변수입니다.
일반적인 구현에서는 원래 재귀 함수를 사용해야 합니다. 루프의 종료 조건은 정확히 재귀의 종료 조건입니다.
원래 재귀 함수를 수정하지 않고 재귀 함수의 매개 변수를 스택에 푸시하려면 함수 매개 변수를 얻기 위해 호출되는 재귀 함수 대신 함수를 사용해야 합니다.
재귀 함수마다 종료 조건이 다르지만 다시 재귀 함수가 호출되지 않으면 종료 조건에 도달했다는 의미입니다. 즉, 종료조건은 재귀함수 호출과 관련된다. 재귀 함수가 호출될 때마다 매개변수가 스택에 푸시됩니다. 따라서 스택에 요소가 있는지 여부를 통해 종료 조건 도달 여부를 유추할 수 있습니다.

js 꼬리 재귀 최적화 코드 공유

관련 기사