210606再帰関数のmoreについて...
4981 ワード
再帰関数とメモリ使用量の関係(JavaScript再帰メモリ漏洩)
関数を再帰的に呼び出して問題を解決する方法は、コードが簡潔で、意図が理解しやすいという利点がある.しかし,再帰関数のcallスタックが深いほどメモリオーバーヘッドが大きくなるという欠点もある.
テール再帰(jsのテール再帰)
この問題を解決するための再帰呼び出し方式を末尾再帰と呼ぶ.
簡単に言えば
戻り関数の実行結果は、演算ではなく、すぐに戻る/戻りコマンドに遭遇する前に呼び出す(Tail call)
これにより、前の関数の状態を維持する必要がなくなり、再帰関数が記述されます.(末尾の作業を再開するには、プラットフォームがTCO(Tail Call Optimization)をサポートする必要があります.残念ながら、safari以外のすべてのブラウザでTCOはサポートされておらず、nodeでもTCOはサポートされていません.)
「前」または「最後」の位置概念は、コンパイル前のコードの概念ではなく、実際のスタックフレームが以前の位置を割り当て解除します.
したがって、次の場合はコードの末尾にありますが、Tail Callには適用されません.
// 일반 재귀
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
//----------------------------------------------------
// 꼬리 재귀
function factorial(n, total = 1) { // default parameter :total이 제공되지 않으면 기본값으로 1을 할당한다
if (n === 0) {
return total
}
return factorial(n - 1, n * total)
}
//2개의 인자를 전달하고 있다. 다음 팩토리얼을 계산하기 위한 수인 (n - 1), 그리고 누적된 총합 n * total 이다.
//현재 상태를 실행하기 위한 모든 값 (누적된 값과 다음 팩토리얼 값)을 다 갖고 있기 때문에
//다음 호출이 더이상 이전 호출에 의존적이지 않음
//-----------------------------------------------
return func(n--); // 꼬리 호출이 아니다. (호출이 일어난 뒤, n의 감소가 이루어진다)
// 만약 위 코드가 `return func(--n)` 였다면, 꼬리 호출이다.
末尾再帰関数を作成するテクニックは、次の呼び出しに必要なすべてのステータスをユーザーに渡して、前のフレームを削除することです.単一の関数だけではないので、末尾に再入力可能なネストされた関数を作成できるかどうかも考えられます.もう1つは、適切な末尾呼び出しがコードの実行を速めるとは限らないことを覚えておいてください.実際、ほとんどの場合、かえって遅くなります.
ただし、末尾関数を使用すると、より少ないメモリでスタックできるだけでなく、ローカル(ローカル)に割り当てられたオブジェクトも使用できるので、より少ないメモリで再帰関数を実行できます.
TCO(Tail Call Optimization)
前回の呼び出しで[タグ呼び出し](Tag Calls)が呼び出された場合、新しいスタックフレームを繰り返し作成する必要はありません.
これは、同じスタックフレーム内で再度呼び出された関数のエントリポイントからJump操作(スタックフレームの再利用セキュリティ)を行うことができることを意味します.
次に、再帰的に、すなわち、自分の関数を呼び出してコマンドの最後に位置する場合、これをTail Recursionと呼ぶ.
Tail Recursion Elimination
特定のTCO(Tail Call Optimization)の場合、ある関数が末尾関数である場合、それはキャンセルされます.
これは,反複文の形式で再構成できることを意味する.
多くの人は、末尾再帰的な形で実現すると、Tail Recursion Elificationにつながると勘違いしている.
これは、実際のコンパイラで最適化しないと、通常の再帰のように通常の呼び出しを行うように再構成できることを意味します.
整理したブログ!
ハノイの塔材帰(js塔of hanoi in recursion)
コンビネーション再帰関数
これは、組合せとソートの根本的な違いです.順序の有無
異なるN個の数字からR個を抽出する数と順序は関係ない[1, 2, 3] = [3, 2, 1]
配列の初めに1つずつ選択(固定)し、後の配列に対して組み合わせて貼り付けを求めればよい.再帰関数に入るパラメータで1つ減らします.
Reference
この問題について(210606再帰関数のmoreについて...), 我々は、より多くの情報をここで見つけました https://velog.io/@nala723/210606재귀함수에-대한-moreテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol