함수 꼬리 호출 및 꼬리 귀속
일반적으로 함수 호출 은 메모리 에 '호출 기록' 을 형성 하고 '호출 프레임' (call frame) 이 라 고도 부 르 며 호출 위치 와 내부 변수 등 정 보 를 저장 합 니 다.함수 A 내부 에서 함수 B 를 호출 하면 A 의 호출 프레임 위 에 B 의 호출 프레임 이 형성 된다.B 실행 이 끝나 면 결 과 를 A 로 되 돌려 야 B 호출 프레임 이 사라 집 니 다.만약 에 내부 에서 함수 C 를 호출 한다 면 C 의 호출 프레임 이 하나 더 있 는데 이런 식 으로 유추 할 수 있다.모든 호출 프레임 은 '호출 스 택' (call stack) 을 형성 합 니 다.
꼬리 호출 은 함수 의 마지막 작업 이기 때문에 외층 함수 의 호출 프레임 을 보류 할 필요 가 없습니다. 호출 위치, 내부 변수 등 정 보 는 더 이상 사용 되 지 않 기 때문에 내층 함수 의 호출 프레임 을 직접 사용 하여 외층 함수 의 호출 프레임 을 대체 하면 됩 니 다.
function f() {
let m = 1;
let n = 2;
return g(m + n)
}
//
function f() {
return g(3);
}
f()
//
g(3)
위의 코드 에서 함수 g 가 끝 호출 이 아니라면 함수 f 는 내부 변수 m 와 n 의 값 을 저장 해 야 합 니 다. 그러나 g 를 호출 한 후에 함수 f 가 끝 났 기 때문에 마지막 단계 까지 실행 하면 f (x) 의 호출 프레임 을 완전히 삭제 하고 g (3) 의 호출 프레임 만 유지 할 수 있 습 니 다.
이것 은 바로 '꼬리 호출 최적화' (Tail calloptimization) 라 고 합 니 다. 즉, 내부 함수 의 호출 프레임 만 유지 합 니 다. 만약 에 모든 함수 가 꼬리 호출 이 라면 매번 실행 할 때 호출 프레임 은 한 가지 만 있 습 니 다. 이것 은 메모 리 를 크게 절약 할 것 입 니 다. 이것 이 바로 '꼬리 호출 최적화' 의 의미 입 니 다.
외부 함수 의 내부 변 수 를 사용 하지 않 아야 내부 함수 의 호출 프레임 이 외부 함수 의 호출 프레임 을 대체 할 수 있 습 니 다. 그렇지 않 으 면 '꼬리 호출 최적화' 를 할 수 없습니다.
function addOne(a) {
let one = 1;
function inner(b) {
return b + one
}
return inner(a)
}
위의 함 수 는 끝 호출 최적화 되 지 않 습 니 다. 내부 함수 inner 는 외부 함수 addOne 의 내부 변 수 를 사 용 했 기 때 문 입 니 다.
후처
함수 가 자신 을 호출 하여 재 귀 라 고 합 니 다.만약 에 자신 을 꼬리 호출 하면 꼬리 재 귀 라 고 합 니 다.
재 귀 는 수천 수백 개의 호출 프레임 을 동시에 저장 해 야 하기 때문에 '스 택 넘 침' 오류 가 발생 하기 쉽다 (stack overflow).그러나 꼬리 재 귀 에 있어 서 호출 프레임 만 존재 하기 때문이다.그래서 '스 택 넘 침' 오류 가 발생 하지 않 습 니 다.
... 을 들다
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1)
}
console.log(factorial(5)); // 120
console.log(factorial(4)); // 24
위의 코드 는 하나의 곱셈 함수 로 n 의 곱셈 을 계산 하 는데 최대 n 개의 호출 기록 을 저장 해 야 한다.마지막 재 귀적 으로 바 꾸 면 호출 기록 만 남 겨 두 세 요.
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
};
console.log(factorial(5, 1)); // 120
console.log(factorial(4, 1)); // 24
또 하나의 유명한 예 가 있 는데 바로 Fibonacci 수열 (피 보 나치 수열) 을 계산 하 는 것 도 꼬리 순환 최적화 의 중요성 을 충분히 설명 할 수 있다.
function Fibonacci(n) {
if (n <= 1) { return 1 };
return Fibonacci(n - 1) + Fibonacci(n - 2)
}
console.log(Fibonacci(10)); //89
console.log(Fibonacci(100)); //
마지막 호출 최적화 후의 Fibonacci 수열 은 다음 과 같다.
function Fibonacci(n, ac1 = 1, ac2 = 1) {
if (n <= 1) { return ac2 };
return Fibonacci(n - 1, ac2, ac1 + ac2);
}
console.log(Fibonacci(10)); //89
console.log(Fibonacci(30)); //1346269
console.log(Fibonacci(100)); //10946
'꼬리 호출 최적화' 는 재 귀 작업 에 큰 의 미 를 가지 기 때문에 일부 함수 식 프로 그래 밍 언어 는 이 를 언어 규격 에 기록 했다.첫 번 째 로 모든 ECMAScript 의 실현 은 반드시 '꼬리 호출 최적화' 를 배치 해 야 한다 고 명확 하 게 규정 했다.즉, ES6 에서 끝 재 귀 만 사용 하면 스 택 넘 침 이 발생 하지 않 고 메모리 가 상대 적 으로 절약 된다 는 것 이다.
재 귀 함수 재 작성
끝 재 귀적 실현 은 종종 재 귀적 함 수 를 바 꾸 어 마지막 단계 에서 자신 만 호출 할 수 있 도록 해 야 한다.이 를 실현 하 는 방법 은 모든 내부 변 수 를 함수 의 매개 변수 로 바 꾸 는 것 이다. 예 를 들 어 위의 예 와 같다.단계 곱 하기 함수 factorial 은 중간 변수 totalk 을 사용 해 야 합 니 다. 그러면 이 중간 변 수 를 함수 의 매개 변수 로 바 꾸 는 것 이 단점 입 니 다. 이렇게 하 는 것 은 관여 하지 않 고 첫눈 에 알 아 보기 어렵 습 니 다. 왜 5 의 단 계 를 계산 하 는 지 두 개의 매개 변수 5 와 1 을 입력 해 야 합 니 다.
function tailFactorial(n, total) {
if (n === 1) return total;
console.log(n - 1, n * total);
/**
* 4 5
* 3 20
* 2 60
* 1 120
*/
return tailFactorial(n - 1, n * total)
}
function factorial(n) {
return tailFactorial(n, 1)
}
factorial(5)
위의 코드 는 정상 적 인 형식의 계승 함수 factorial 을 통 해 꼬리 재 귀 함수 tailFactorial 을 호출 하면 훨씬 정상 적 으로 보 입 니 다.
함수 식 프로 그래 밍 은 코 리 화 (currying) 라 는 개념 이 있 는데 다 중 매개 변수의 함 수 를 단일 매개 변수 로 바 꾸 는 것 을 의미한다.여기 도 코 리 화 를 사용 할 수 있어 요.
function currying(fn, n) {
return function(m) {
return fn.call(this, m, n)
}
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total)
}
const factorial = currying(tailFactorial, 1);
console.log(factorial(5));//120
위의 함 수 는 코 리 화 를 통 해 꼬리 재 귀 함수 tail Factorial 을 하나의 매개 변수 만 받 는 factorial 두 번 째 방법 으로 바 꾸 면 훨씬 간단 합 니 다. ES6 의 함수 기본 값 을 직접 사용 합 니 다.
function factorial(n, total = 1) {
if (n === 1) return total;
return factorial(n - 1, n * total)
}
// ， total 1，
console.log(factorial(5)); //120
귀속 은 본질 적 으로 일종 의 순환 조작 이다.순수한 함수 식 프로 그래 밍 언어 는 순환 조작 명령 이 없고 모든 순환 은 재 귀적 으로 이 루어 집 니 다. 이것 이 바로 꼬리 재 귀 는 이러한 언어 에 매우 중요 한 이유 입 니 다. '꼬리 호출 최적화' 를 지원 하 는 다른 언어 에 대해 순환 만 재 귀적 으로 대체 할 수 있 고 재 귀 를 사용 하면 꼬리 재 귀 를 사용 하 는 것 이 좋 습 니 다.
미 순환 최적화 의 실현
꼬리 순환 최적화 는 엄격 한 모델 에서 만 효력 이 발생 하고 정상 적 인 모델 에서 만 효력 이 발생 하거나 이 기능 을 지원 하지 않 는 언어 환경 에서 스스로 꼬리 호출 최 적 화 를 실현 해 야 한다.원 리 는 꼬리 재 귀 를 최적화 시 켜 야 하 는 이 유 는 스 택 을 너무 많이 호출 하여 넘 치 게 하기 때문이다.그러면 스 택 을 줄 이면 넘 치지 않 습 니 다.
"순환" 으로 "재 귀" 를 대체 하 는 정상 적 인 재 귀 함수:
function sum(x, y) {
if (y > 0) {
return sum(x + 1, y - 1)
} else {
return x
}
}
console.log(sum(1, 100000));
//RangeError: Maximum call stack size exceeded
위의 sum 은 재 귀 함수 입 니 다. 매개 변수 x 는 누적 되 어야 하 는 값 입 니 다. 매개 변수 y 는 재 귀 횟수 를 제어 하고 sum 이 100000 번 재 귀 하면 됩 니 다.오류 가 발생 할 수 있 습 니 다. 호출 스 택 의 최대 횟수 를 초과 하면 순환 실행 으로 전환 합 니 다.
function trampoline(f) {
/**
* f ， f
* ， ，
* ，
* */
while (f && f instanceof Function) {
f = f();
}
return f;
}
// sum ， sum ，
function sum(x, y) {
if (y > 0) {
return sum.bind(null, x + 1, y - 1)
} else {
return x
}
}
console.log(trampoline(sum(1, 100000))); //100001
그러나 위의 trampoline 함 수 는 진정한 꼬리 호출 최적화 가 아니 라 아래 에서 실현 해 야 합 니 다.
function tco(f) {
let value;
// ， active （1），
let active = false;
let accumulated = [];
return function accumulator() {
//accumulated sum （3）
accumulated.push(arguments);
if (!active) {
// ， （2）
active = true;
while (accumulated.length) {
// ，sum undefined，
// accumulated sum ， ， while
value = f.apply(this, accumulated.shift());
//shift() ， 。
}
active = false;
return value;
}
}
}
let sum = tco((x, y) => {
if (y > 0) {
return sum(x + 1, y - 1)
} else {
return x
}
});
console.log(sum(1, 100000)); //100001
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
