재귀

배운점

재귀(Recursion)

원래의 자리로 되돌아가거나 되돌아옴.
함수 내부에 자기 자신을 호출하는 메소드

재귀 함수의 장점

---

• 불필요하게 여러 개의 반복문을 사용하지 않아 코드가 간결하다
• 변수를 여러개 사용 할 필요가 없다

재귀 함수의 단점

---

• 반복문과 달리 코드의 흐름을 직관적으로 파악하기 어렵다.
• 반복하여 메소드를 호출하면 변수, 반환값이 스텍 영역에 저장되어
  과도하게 호출하게 되면 메모리를 더 많이 사용하게 된다
• 메소드를 종료할 때 복귀를 위한 컨텍스트 스위칭 비용이 발생한다

재귀 함수를 사용하기 위한 조건

---

문제를 작은 단위로 쪼갤 수 있어야 한다 -> recursion case
재귀 호출이 종료되는 시점이 있어야 한다 -> base case

재귀적으로 사고 하는 방법

---

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고 경우의 수를 나누기
3. 단순한 문제 해결하기
4. 복잡한 문제 해결하기
5. 코드로 구현하기

실습

package Recursion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class ColorPaper {

    public static int blue = 0;
    public static int white = 0;
    public static int[][] board;

    public static  void paper(int row, int col, int size) {

        // 체크가 트루일 때
        if(check(row, col, size)) {
            // 첫번째 요소가 0 일 때
            if(board[row][col] == 0)
                white++;
            // 두번째 요소가 1 일 때
            else
                blue++;

            return;
        }

        // 사이즈를 나눈다
        size = size / 2;

        // 좌상단
        paper(row, col, size);
        // 우상단
        paper(row, col + size, size);
        // 좌하단
        paper(row + size, col, size);
        // 우하단
        paper(row + size, col + size, size);

    }

    public static boolean check(int row, int col, int size) {
        for(int i = row; i < row + size; i++) {
            for(int j = col; j < col + size; j++) {
                if(board[row][col] != board[i][j])
                    return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        
        board = new int[n][n];

        // 이차원 배열을 입력 받는다
        for(int i = 0; i < n; i++) {
            String line = bf.readLine();
            StringTokenizer st = new StringTokenizer(line);
            for(int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // parper함수에 넣는다
        paper(0, 0, n);

        System.out.println(white);
        System.out.println(blue);

    }
}

백준_색종이 만들기

느낀점

---

그동안 알고리즘이나 코테를 풀 때 수도 코드를 생략하고 작성했었다.
수도 코드를 작성 하는 편이 실수도 덜 나고 코드 짜기 쉽긴 했지만
귀찮다는 이유 하나로 소외했었었다.

재귀 알고리즘을 공부하면서 머리 속으로만 생각해서 코드를 짜면
앞에 내용과 뒤의 내용이 헷갈리기 시작해서 코드가 꼬이기 시작했다.

요즘 백준 실버 상위, 골드 하위 문제를 풀면서 위의 문제가 많아지기 시작했는데
오늘 수도 코드를 이용해서 푼 문제가 한번만에 통과하는 것을 보고
수도 코드의 작성의 중요성을 알게 되었고
재귀도 멀리 보면 어렵지만 하나하나 차근차근 풀어보면
충분히 풀 수 있다는 자신감이 들었다.

재귀 어려운 내용이지만 꼭 익숙해저셔 자신 있게 풀 수 있는 날이 왔으면 좋겠다