Recursion


いわゆる「再帰」(Recursion)


これは自分を呼び出す関数です.Base caseとRecursive caseに区分され、Base caseは結果を簡単に返す部分であり、Recursive caseは自己呼び出しの部分である.
int factorial(int n) {

	// Base case
	if(n == 0)
    	return 1;
    
    // Recursive case
    return n * factorial(n-1);    
}
  • stack memory
  • 再帰と注釈の作成(フィボナッチを使用)


    再計算すると、計算した値を配列に保存し、求めた計算は計算ではなくインポートされます.
    public class Main4 {
    
        static int[] fibo;
        public int DFS(int n){
    
            if(fibo[n] > 0) return fibo[n];
            if (n == 1) return fibo[n]=1;
            else if (n == 2) return fibo[n]=1;
            else {
                return fibo[n] = DFS(n-2) + DFS(n-1);
            }
        }
    
        public static void main(String[] args) {
            Main4 T = new Main4();
            int n = 45;
            fibo = new int[n+1];
            T.DFS(n);
            for(int i = 1; i <= n; i++) {
                System.out.print(fibo[i] + " ");
            }
        }
    }

    Flood fillアルゴリズム


    任意の位置で左右に再帰的に呼び出されるアルゴリズム.以下は任意の位置から始まり、0は空の1は壁を表し、エッジインタフェースや1に遭遇する前に1で埋め込まれた部分を表します.
    public class recursiveEx1 {
    
        static int N;
        static int[][] Board = new int[100][100];
        static void fill(int row, int col) {
            // Base case
            if(row < 0 || row > N-1 || col < 0 || col > N-1){
                return;
            }
    
            // 벽을 만났거나 이미 1로 마킹 되어 있는 경우이므로 return
            if(Board[row][col] != 0){
                return;
            }
    
            Board[row][col] = 1;
    
            // 위로 올라가는 부분
            fill(row-1, col);
    
            // 아래로 가는 부분
            fill(row+1, col);
    
            // 왼쪽으로 가는 부분
            fill(row, col-1);
    
            // 오른쪽으로 가는 부분
            fill(row, col+1);
    
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            N = sc.nextInt();
    
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    Board[i][j] = sc.nextInt();
                }
            }
    
            // 시작 위치
            int sRow, sCol;
            sRow = sc.nextInt();
            sCol = sc.nextInt();
    
            fill(sRow, sCol);
    
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++) {
                    System.out.print(Board[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
    *参考資料-https://www.youtube.com/watch?v=McbJoGMoVoY