tamakipedia

フロントエンドエンジニア。Typescriptもう特訓中です。一日の振り返りや学んだことをちょっとずつ吐いています。

再帰についてのまとめ

再帰についての章を学習したので、
そのまとめ。

再帰について

再帰とは自身を関数として呼び出す処理のこと。

足し算がわかりやすい例です。
例えば 5 + 5 のような加算も 5 + 1 + 1 + 1 + 1 + 1 とすることで
「5に1を足す」を繰り返している処理だと気づくことができます。

プログラミングに直すと

function numberAddition(x, y){
    // yがゼロになると終わり
    if(y <= 0){
        return x;
    }

    return numberAddition(x+1,y-1);
}

このような形を取ります。
(numberAdditionが何回も呼び出され、引数は xが一ずつ増加、yが一ずつ減少する)

図にするとこのような形です。

f:id:okinawanpizza:20210812075517p:plain

このような形で、自身を関数として呼び出す形を再帰(再帰的計算)とよびます。
また、ループを終了して戻り値を出力する処理をベースケースと言います。

まさに再帰を使って少しずつ切り崩すような処理を行うことができます。

例として以下のような文字列を逆から表示する関数を作成しました。
入力 konnichiwa に対して "awihcinnok" を返すような処理です。

function reverseString(string){
    if(string.length == 1){
        return string;
    }
    //終わり
    return string[string.length - 1] + reverseString(string.substring(0,string.length - 1));
}

図のような形で出力しているのですが、中身をみてみると
「最後の文字を出力+自身の呼び出し」で成り立っていることがわかります。
f:id:okinawanpizza:20210812083028p:plain

最大公約数のアルゴリズム

mod と言う余剰演算子を用いて、以下のような公式で表現することができます。

gcd(m,0) = m            
gcd(m,n) = gcd(n, m mod n)

これは数字の大きい方を小さい方で割り続け、
初めて両方の数字が等しくなった時の値を算出する公式。
ユークリッドアルゴリズムというんだとか。

これも自身を呼び出しているので再帰関数。

この章で学んだ単語

再帰

自身を関数としてもう一度呼び出す処理のこと

・ベースケース

再帰的計算の処理の中で、ループを終了させる処理のこと。  
ベースケースを持っていない関数は無限ループに陥る。  

・総和計算

一般的にシグマを使って表すあらわされる、x ~ y の全ての数の和のこと。

・CCD

最大公約数のこと  
ユークリッドアルゴリズムというmodを用いたアルゴリズムを使うとすぐに算出できる