部分和問題から再帰的なプロセスを網羅する

#0. はじめに
深さ優先探索を行うときには、再帰的な書き方をしなければいけない場面が多々あると思います。
実際、他人の書いたコードを見てみると中でreurn文が多用されており、どの順番でコードが動いているのか私には全然分かりませんでした。そこで今回は、具体的にコードの動きを観察します。

#1 . 部分和問題
実際の問題はけんちょんさんの再帰関数を学ぶと、どんな世界が広がるかの記事の3-1を参考にしてください。

ちなみにjavaでのコードはこうなります。

import java.util.Scanner;
public class Main {
	static int indexA = 0;
	static int indexB = 0;
	static boolean func(int i, int x, int[] a) {


		//ベースケース

		if(i == 0) {
			if(x == 0) {
				return true;
			}else {
				return false;
			}
		}


		//a[i-1]を選ばない場合(func(i-1,x,a)がokならok)

		if(func(i-1,x,a)) {
			return true;
		}

		System.out.println("indexA:"+(++indexA)+" i:"+i+" x:"+x);

		//a[i-1]を選ぶ場合(func(i-1,x-a[i-1],a)がokならok)
		if(func(i-1,x-a[i-1],a)) {
			return true;
		}
		
		System.out.println("indexB:"+(++indexB)+" i:"+i+" x:"+x);
		
		//どっちもダメだったらダメ
		return false;



	}


	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.print("コインの枚数:");
		
		int n = stdIn.nextInt();


		int[] a = new int[n];
		
		System.out.println("コインの価値:");
		
		for(int i = 0; i < n; i++) {
			a[i] = stdIn.nextInt();
		}
		
		System.out.print("金額の設定:");
		int x = stdIn.nextInt();
		
		//再帰的に書く
		
		if(func(n,x,a)) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
		
		

	}

}

##1.1 n = 3, a =(2,3,4) x = 6 のとき

なぜこのような順番でコードが出てきたかを以下の図で確認できます。

〇の中に書かれた順番で動いているのが分かると思います。

※ここからさらに詳細な動きを書くので、理解できた方は次の見出しまでスキップしてください。

iが0のとき、xが0でない場合は、すべてfalseが返るので、①のfunc(0,6)はfalseが返る、そのためfunc(1,6)のとき、の最初の1個目のif文はif(false)であるため、何も何も表示されない。

if(func(i-1,x,a)) {  //ここが表示されない

			System.out.println("選ばない"+" i:"+i+" x:"+x);

			return true;
		}

次に, i==1,x == 6を今見ているので、表示されているのが分かる。

System.out.println("indexA:"+(++indexA)+" i:"+i+" x:"+x+"\n"); //1行目に ""indexA:1 i:1 x:6""と表示されている

この後、func(1,6)の2つ目のif文の②が動作しており、func(0,4)はfalseであるため、このif文も表示されない。

if(func(i-1,x-a[i-1],a)) { //ここが表示されない

			System.out.println("選ぶ"+" i:"+i+" x:"+x);

			return true;
		}

そして、そのif文の後のprintlnが動作していることが分かる。(②のindexB:1 i:1 x:6が表示されている)

System.out.println("indexB:"+(++indexB)+" i:"+i+" x:"+x+"\n"); 

func(1,6)のどちらのif文もfalseであったため、//どっちもダメだったらダメと書かれた行のreturn falseが返ってくる。

ここでやっとfunc(2,6)の最初のif文が終わったことを意味するのである。

再帰はベースケースまでたどり着いてから戻り値がどんどん返ってくるイメージを持つと分かりやすいだろう。

##1.2 n = 3, a =(2,3,4) x = 10 のとき
ここで絶対x=10の目標には達しないときの動きも確認する。

この画像から以下のような順番で動いていることが分かる。

深さ優先探索が行われていることがよくわかると思う。先程と同じようなコードの動きをしているので説明は省略する。

#2 まとめ
再起関数を用いるときは、まず ベースとなるケースを考えて循環を止める。
その後、if文内で再帰を行い、trueになるケースが一つでも存在するかを確かめた。

bit全探索もとる、とらないの2^n通りのケースを考えられるため、今回の問題であればbit全探索でも再帰的に書いても良いとは思います。
しかし、if文でさらに分岐した条件を書くことができる点が再帰のさらなる魅力だと思います。(まだ使ったことはありませんが...。)