どうもこんにちは!
サバ缶(@tech_begin)です。
基本情報や応用情報技術者試験で頻出する「プログラムの特性」に関する問題。
今回はその特性の1つである「リカーシブ」について解説していきます。
もし分かりづらい箇所や、間違っている箇所があればお気軽にTwitterへご連絡ください!
プログラム特性とは
それではまず、少しおさらいをしておきましょう。
すでに何があるのか知っている方は、飛ばして大丈夫です!
プログラムの構造上 生じる性質を分類したのが「プログラムの特性」です。
その「プログラムの特性」は4つに分類されます。
- リロケータブル(再配置可能)
- リユーザブル(再使用可能)
- リエントラント(再入可能)
- リカーシブ(再帰的)
このうちの1つ『リカーシブ(再帰的)』について学んでいきます。
リカーシブ(再帰的)とは
リカーシブとは、自分自身を呼び出すことができる特殊な性質を持ったプログラムのことです。
リカーシブは英語で「recursive」と書き、日本語で「再帰」と言います。
そして「リカーシブ」という性質を持ったプログラムを『再帰的プログラム』と呼びます。
「cursive」は『草書・筆記体』という意味があります。
筆記体で一筆書きのようにサラサラーっと書いた後、点などを付け足すために最初に戻ります。
その様子から「Recursive」という言葉が「再帰」と意味するようになったようです。
…にしても「再び帰るプログラム」ってどういうこと?
さらに詳しく見ていきましょう!
再帰的とは
リカーシブとは、自分自身を呼び出すことができる特殊な性質を持ったプログラムのことでした。
自分自身を呼び出すって、どういうこと?
そう思われるのも仕方ありません。
プログラミングを学習されている方でしたら、再帰的プログラムを作ったこともあると思います。
以下のようなプログラムです。
public class Main {
public static void main(String[] args) {
System.out.println(factorial(5));
}
/**
* 引数の階乗を求める
* @param n 階乗する値
*/
public static void factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1); // factorial自身を呼び出す
}
}
}
ここでは、引数で受け取った値の階乗を求めるプログラムを書いています。
このプログラムが行なっている処理をイメージしてみましょう!
1から指定の数まで全てを掛け合わせる計算方法のことです。
例えば指定された数が「5」であれば「1×2×3×4×5」という計算を行うことを階乗と言います。
まず赤色のルートで処理を深堀していきます。トンネルを掘っていっているイメージですね。
すると右端で「0」に到達します。いわば「折り返し地点」ですね。
ここから青色のルートを辿っていくのですが、同時に計算結果を戻り値として返却していきます。
最終的に呼び出し元に戻ってきて(再帰)、計算結果である「6」が算出されるというわけです。