1前書き

この記事では、あらゆるプログラミング言語の中核となる概念、つまり再帰に焦点を当てます。

再帰関数の特性を説明し、Javaでさまざまな問題を解決するために再帰を使用する方法を説明します。


2再帰を理解する


2.1. 定義

Javaでは、関数呼び出しメカニズムは、

メソッド呼び出し自体を持つ可能性

をサポートします。この機能は__再帰として知られています。

たとえば、0から何らかの値

n

までの整数を合計したいとします。 

public int sum(int n) {
    if (n >= 1) {
        return sum(n - 1) + n;
    }
    return n;
}

再帰関数には、主に2つの要件があります。


  • 停止条件

    – 特定の条件が満たされると関数は値を返します

さらなる再帰呼び出しなしで、条件は満たされます


再帰呼び出し** – 関数は

入力

を使って自分自身を呼び出します。

停止条件により近いステップです

各再帰呼び出しは、JVMのスタックメモリに新しいフレームを追加します。

そのため、

再帰呼び出しがどれだけ深く潜ることができるかに注意を払わないと、メモリ不足の例外が発生する可能性があります。

この潜在的な問題は、末尾再帰最適化を活用することで回避できます。


2.2. 尾の再帰対頭部の再帰

再帰呼び出しが最後に実行される関数である場合、再帰関数を

tail-recursion

** と呼びます。それ以外の場合、

head-recursion

と呼ばれます。

上記の

sum（）

関数の実装は、ヘッドの再帰の例であり、末尾の再帰に変更できます。 

public int tailSum(int currentSum, int n) {
    if (n <= 1) {
        return currentSum + n;
    }
    return tailSum(currentSum + n, n - 1);
}

末尾再帰では、** 再帰呼び出しはメソッドが最後に行うことなので、現在の関数内で実行するものはありません。

したがって、論理的には現在の関数のスタックフレームを保存する必要はありません。

コンパイラはこの点を利用してメモリを最適化することができますが、Javaコンパイラは現在のところ末尾再帰を最適化していないことに注意してください。


2.3. 再帰と反復

再帰は、コードをより明確で読みやすくすることによって、いくつかの複雑な問題の実装を単純化するのに役立ちます。

しかし、すでに説明したように、再帰的アプローチでは、再帰呼び出しごとに必要なスタックメモリが増えるため、多くのメモリが必要になります。

別の方法として、もし再帰を使って問題を解くことができれば、反復によってそれを解くこともできます。

たとえば、

sum

メソッドは反復を使用して実装できます。 

public int iterativeSum(int n) {
    int sum = 0;
    if(n < 0) {
        return -1;
    }
    for(int i=0; i<=n; i++) {
        sum += i;
    }
    return sum;
}

再帰と比較して、反復的なアプローチは潜在的により良いパフォーマンスを与えるかもしれません。そうは言っても、反復は再帰と比較してより複雑で理解しにくくなります。

二分木をたどる。

ヘッドの再帰、テールの再帰、そして反復的なアプローチの間で正しい選択をすることはすべて特定の問題と状況に依存します。


3例

それでは、いくつかの問題を再帰的に解決してみましょう。


3.1. 10のn乗を求める

10のn乗を計算する必要があるとします。ここでの入力はnです。再帰的に考えると、最初に10のn（1）乗を計算し、その結果に10を掛けることができます。

次に、10の

（n-1）

乗を計算すると、10の

（n-2）

乗になり、その結果に10を掛けます。 10の（n-n）乗、つまり1を計算する必要がある時点まで、このようにしていきます。

これをJavaで実装したい場合は、次のように書きます。 

public int powerOf10(int n) {
    if (n == 0) {
        return 1;
    }
    return powerOf10(n-1) **  10;
}


3.2. フィボナッチ数列

のn番目の要素の検索


0

と

1

で始まる**

フィボナッチ数列

は、各数がそれに続く2つの数の合計として定義される数の列です。

それで、番号

n

が与えられると、私たちの問題は

Fibonacci Sequence

の

n

番目の要素を見つけることです。

再帰的な解決策を実行するために、

Stop Condition

と



Recursive Call

.

を理解する必要があります。

幸いにも、それは本当に簡単です。


f（n）

をシーケンスのn番目の値と呼びましょう。それでは、

f（n）= f（n-1）f（n-2）

（

再帰呼び出し

）__とします。

一方、

f（0）= 0および

f（1）= 1（

Stop Condition）

それで、問題を解決するために再帰的な方法を定義することは私たちにとって本当に明白です: 

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}


3.3. 10進数から2進数への変換

それでは、10進数を2進数に変換する問題を考えてみましょう。要件は、正の整数値

n

を受け取り、バイナリの

String

表現を返すメソッドを実装することです。

10進数を2進数に変換する1つの方法は、値を2で除算し、残りを記録して、商を2で除算し続けることです。

商が

0

になるまで、このように分割し続けます。次に、すべての残りを予約順に書き出すことで、バイナリ文字列を取得します。

したがって、私たちの問題はこれらの残りを予約順に返すメソッドを書くことです。 

public String toBinary(int n) {
    if (n <= 1 ) {
        return String.valueOf(n);
    }
    return toBinary(n/2) + String.valueOf(n % 2);
}


3.4. 二分木の高さ

二分木の高さは、根から最も深い葉までの辺の数として定義される。私たちの問題は、与えられた二分木に対してこの値を計算することです。

1つの単純なアプローチは、最も深い葉を見つけて、それから根とその葉の間のエッジを数えることです。

しかし、再帰的な解決策を考えようとすると、二分木の高さの定義を根の左枝と根の右枝の最大高さに

1

を加えたものとして言い換えることができます。

根に左枝と右枝がない場合、その高さは

zero

です。

これが私たちの実装です。 

public int calculateTreeHeight(BinaryNode root){
    if (root!= null) {
        if (root.getLeft() != null || root.getRight() != null) {
            return 1 +
              max(calculateTreeHeight(root.left),
                calculateTreeHeight(root.right));
        }
    }
    return 0;
}

したがって、** いくつかの問題は再帰によって非常に簡単な方法で解決できることがわかります。


4結論

このチュートリアルでは、Javaでの再帰の概念を紹介し、それをいくつかの簡単な例で示しました。

この記事の実装はhttps://github.com/eugenp/tutorials/tree/master/core-java-lang[over on Github]にあります。