[資料構造]Chapter 02.ループ(Recursion,再帰)

1610 ワード
recursion データ構造 ループ 復帰する テキストリンク
🚨 '過去に「C言語で簡単に書ける資料構造」という本を使った授業ノートを整理した.
💡 Chapterの順序は本と同じですが、教授の過去の授業内容によっては他の内容と異なる本もあります.

-関数呼び出しまたは返却時のアドレスの大きな移動:jump
-戻る時:最後に呼び出された場所(呼び出しの逆)に戻ります.

ループ


:関数を定義するときに自分の形式を参照し、大きなサイズの問題を小さなサイズの問題に分解することで解決します.

✓C 2の有無は末尾再帰(ある場合は末尾再帰X、ない場合は末尾再帰O)に区分する
✓全ての循環関数を非循環関数に変換可能
  • サイクル関数の長所と短所
  • の利点:アルゴリズムの設計と実現が容易である.
  • 欠点:遅い可能性がある(<-重複演算がある)
    • ex)フィボナッチ数列

    分割と統合(分割征服法)
    1.分割(Devide):同じタイプの小さいサイズ
    2.征服(征服):個別解決(ループ呼び出し)
    3.連結(combine):総合小結果
    Merge Sort
    Ms(int l, int h) {
	if(l >= h) return // 재귀호출에는 조건 test 필수!! , data 개수 1개 이하는 sorting 필요 X
    m = (l + h)/2
    Ms(l, m)
    Ms(m+1, h)
    Merge(l, m, h) // 병합
}
  • 分析
    • Hanoi Tower Puzzle:ハノイタワー問題

    1.一度にディスクが1つしかない
    2.いつでも大きい
    3.最小移動
    HT(n, S, D, T) {
	if(n = 0) return
    HT(n-1, S, T, D)
    S -> D
    HT(n-1, T, D, S)
}
  • 分析
    • [アルゴリズム]Bubble Sort
    [セットトップ]カスタムネットワーク要求エンジン