Ch02. 復帰する


02-1. 関数の再帰呼び出しについて


再帰関数かいきかんすう:関数内で独自の関数を再呼び出しかんすう
void recursive(void)
{
    printf(“Recursive call! \n”);
    recursive();
}

関数を構成する文は、CPUに移動(コピー)することで実行されます.

家に帰る条件

#include <stdio.h>

void Recursive(int num)
{
    if (num <= 0) // 재귀의 탈출 조건
    {
        return; // 재귀의 탈출!
    }
    printf("Recursive call! %d \n", num);
    Recursive(num-1);
}

int main(void)
{
    Recursive(3);
    return 0;
}

貴重な設計事例

  • 工場
    整数nの工場:n!=n x (n-1) x (n-2) x … x 3 x 2 x 1

  • nが1より大きい場合は
  • である.
    if(n >= 1) return n * factorial(n-1)
  • nが0の場合
  • if(n == 0) return 1;
    階乗関数
    #include <stdio.h>
    int Factorial(int n)
    {
        if(n == 0) return 1;
        else return n*Factorial(n-1);
    }

    02-2. リサイクル


    フィボナッチ数列:Fibonacciシーケンス


    フィボナッチ数列の展開:0、1、1、2、3、5、8...
    前の2つを合わせて現在の数を創造する過程.
    数列のn番目の値=数列のn-1個の値+数列のn-2個の値
    #include <stdio.h>
    int Fibo(int n)
    {
        if(n == 1) return 0;
        else if(n == 2) return 1;
        else return Fibo(n-1) + Fibo(n-2);
    }

    フィボナッチ関数の展開過程



    バイナリナビゲーションアルゴリズム


    バイナリナビゲーションアルゴリズムモード
    1.目標値がナビゲーション範囲の中央に格納されていることを確認する
    2.保存されていない場合は、ナビゲーション範囲を半減してナビゲーションを再開します.
    ナビゲーションに失敗しました
    ナビゲーション範囲の開始位置を示す「前」は、ナビゲーション範囲の終了を示す「前」よりも大きい.
    #include <stdio.h>
    int BsearchRecur(int ar[], int first, int last, int target)
    {
        int mid;
        if(first > last)
        {
            return -1;  // -1의 반환은 탐색의 실패를 의미
        }
        mid = (first + last) / 2;  // 탐색 대상의 중앙을 찾는다
        
        if(ar[mid] == target)
        {
            return mid; // 탐색된 타겟의 인덱스 값 반환
        }
        else if(ar[mid] > target)
        {
            return BsearchRecur(ar, first, mid-1, target);
        }
        else
        {
            return BsearchRecur(ar, mid+1, last, target);
        }
    }

    02-3. ハノイタワー:The Tower of Hanoi


    ハノイタワーの問題を理解する


    1本の棒に積み上げられた円盤を別の円盤に移動する方法

    条件
  • ディスクは1つにつき1つしか移動できません.
  • の移動中、小さな円盤には大きな円盤は存在しない.
  • プロセス

    2つの円盤をレバーBに持ち上げると、3番の円盤をレバーCに持ち上げることができます

    繰り返しモード



    3つの円盤をロッドBに持ち上げると、4番の円盤をロッドCに持ち上げることができます

    ハノイタワーのトラブルシューティング

  • 小さな円盤(底部円盤を除く残りの円盤)をAからBに移動
    1つの
  • の大きな円盤(底部円盤)をAからC上の
  • に移動する.
  • 小さなディスクn-1(上のステップ1から取り出したディスク)をBからCに移動
    void HanoiTowerMove(int num, char from, char by, char to)
    {}
    num個の円盤を経て、移動開始から
    脱出条件
    移動するディスクの数は1です.
    #include <stdio.h>
    void HanoiTowerMove(int num, char from, char by, char to)
    {
        if(num == 1)
        {
            printf("원반 1을 %c에서 %c로 이동\n", from, to);
            
        }
        else
        {
            HanoiTowerMove(num-1, from, to, by);
            printf("원반 %d를 %c에서 %c로 이동 \n", num, from, to);
            HanoiTowerMove(num-1, by, from, to);Think
        }
    }