Download presentation
Presentation is loading. Please wait.
1
再帰的手続き
2
再帰 自分自身を参照すること。 再帰的な定義 再帰的な手続き ユダヤ人とは、ユダヤ教徒であるか、 ユダヤ人を母とする者。
自分自身を呼び出す手続き。 常に自分を呼び出していては停止しない。 static void loop() { loop(); }
3
組み合わせの数 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; }
4
クイックソート 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 void quicksort(int[] a, int p, int q) {](http://slidesplayer.net/slide/16466694/96/images/4/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88+static+void+quicksort%28int%5B%5D+a%2C+int+p%2C+int+q%29+%7B.jpg "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);")
5
変数について メソッドの中で宣言される変数は、そのメソッドに局所的であり、メソッドの呼出しごとに別の領域が割り当てられる。
従って、再帰呼び出しの間で変数が混乱することはない。 このようなメソッドに局所的な変数の他に、クラスのメソッドの間で共有される変数がある。 static int n; これは、スタティック変数という。
6
バックトラック 再帰的な手続きを用いると、 パズルの解の探索など、 後戻りしながら場合を尽くす過程を 簡単に実現することができる。
参考例：８クイーンのパズル
Similar presentations
