Funtionl-Light-JS----Recursion
2766 ワード
再帰する再帰的定義 再帰のメリット 相互再帰 再帰の弊害 尾呼び出し 再帰的最適化 再帰的な定義
再帰的とは、関数が内部で自身を呼び出し、再帰的な循環呼び出しを終了する条件があるということです.
再帰的な利益
再帰的には、私たちのコードは、より良い読み取り可能性があります.
相互再帰(Mustual Rescursion)とは、2つ以上の関数が再帰的ループで相互に呼び出されるとき、これを相互再帰的と呼ぶ.example:
再帰的にはヒープメモリのリークを引き起こす可能性がある.
エンドコール
関数の最後のステップが関数呼び出しである場合、私たちはテイルコールと呼びます.ES 6には、PTC(Proper Tail Calls)という、適切なテイルコールがある.JSエンジンは、このような呼び出しを最適化する.ES 6の最終再帰最適化はもう一つの重要な前提があります.厳格なモードでなければなりません.もう一つの概念はテイルコール最適化といいます.英語の原文はテールCall Optimzations(TCO)です.は再帰的にテールコール最適化の形に変換する.このような最適化は、可能な場合には、我々の関数をテールコールの形に変換することであることがよく理解される. トランポリン関数を使用してトランポリン(Trampoline)関数の本質は、関数を返すと、ループが続き、関数を実行して、その戻りを捕まえて、そのタイプを確認することです.関数でない場合は、トランポリンは関数呼び出しが完了したと仮定して値を返します. は、連続伝達関数の形式的な連続伝達関数を使用して、この最適化の本質はやはり尾呼び出し最適化を使用している.コードを組織して、各関数が他の関数を受信して、その末尾で実行させます.これをリレーパターン(CPS)と呼びます.これはフィbcoの数列に対する再帰的最適化の例です.
再帰的とは、関数が内部で自身を呼び出し、再帰的な循環呼び出しを終了する条件があるということです.
再帰的な利益
再帰的には、私たちのコードは、より良い読み取り可能性があります.
The most commonly cited reason that recursion fits the spirit of FP is because it trades (much of)
the explicit tracking of state with implicit state on the call stack. Typically, recursion is most useful
when the problem requires conditional branching and back-tracking, and managing that kind
of state in a purely iterative environment can be quite tricky; at a minimum, the code is highly
imperative and harder to read and verify. But tracking each level of branching as its own scope
on the call stack often significantly cleans up the readability of the code.
相互再帰(Mustual Rescursion)とは、2つ以上の関数が再帰的ループで相互に呼び出されるとき、これを相互再帰的と呼ぶ.example:
function isOdd(v) {
if (v === 0) return false;
return isEven( Math.abs( v ) - 1 );
}
function isEven(v) {
if (v === 0) return true;
return isOdd( Math.abs( v ) - 1 );
}
再帰的にはヒープメモリのリークを引き起こす可能性がある.
エンドコール
関数の最後のステップが関数呼び出しである場合、私たちはテイルコールと呼びます.ES 6には、PTC(Proper Tail Calls)という、適切なテイルコールがある.JSエンジンは、このような呼び出しを最適化する.ES 6の最終再帰最適化はもう一つの重要な前提があります.厳格なモードでなければなりません.もう一つの概念はテイルコール最適化といいます.英語の原文はテールCall Optimzations(TCO)です.
//These are not PTC:
foo();
return;
// or
var x = foo( .. );
return x;
// or
return 1 + foo( .. );
//PTC
return x ? foo( .. ) : bar( .. );
function trampoline(fn) {
return function trampolined(...args) {
var result = fn( ...args );
while (typeof result == "function") {
result = result();
}
return result;
};
}
var sum = trampoline(
function sum(num1,num2,...nums) {
num1 = num1 + num2;
if (nums.length == 0) return num1;
return () => sum( num1, ...nums );
}
);
var xs = [];
for (let i=0; i<20000; i++) {
xs.push( i );
}
sum( ...xs ); // 199990000
"use strict";
function fib(n,cont = identity) {
if (n <= 1) return cont( n );
return fib(
n - 2,
n2 => fib(
n - 1,
n1 => cont( n2 + n1 )
)
);
}