再帰的手続き
再帰 自分自身を参照すること。 再帰的な定義 再帰的な手続き ユダヤ人とは、ユダヤ教徒であるか、 ユダヤ人を母とする者。 自分自身を呼び出す手続き。 常に自分を呼び出していては停止しない。 static void loop() { loop(); }
組み合わせの数 m個の中からn個を選ぶ組み合わせの数 漸化式 mCn = 1 (n=0 or n=m) mCn = m-1Cn-1 + m-1Cn (0<n<m) static int comb(int m, int n) { if (n == 0) return 1; if (n == m) return 1; int c1 = comb(m-1, n-1); int c2 = comb(m-1, n); return c1+c2; }
クイックソート static void quicksort(int[] a, int p, int q) { int i = p; int j = q; int x = a[(p+q)/2]; do { while (a[i] < x) i++; while (x < a[j]) j--; if (i <= j) { int w = a[i]; a[i] = a[j]; a[j] = w; i++; j--; } } while (i <= j); if (p < j) quicksort(a, p, j); if (i < q) quicksort(a, i, q);
変数について メソッドの中で宣言される変数は、そのメソッドに局所的であり、メソッドの呼出しごとに別の領域が割り当てられる。 従って、再帰呼び出しの間で変数が混乱することはない。 このようなメソッドに局所的な変数の他に、クラスのメソッドの間で共有される変数がある。 static int n; これは、スタティック変数という。
バックトラック 再帰的な手続きを用いると、 パズルの解の探索など、 後戻りしながら場合を尽くす過程を 簡単に実現することができる。 参考例：８クイーンのパズル