재귀

재귀

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

 

재귀 함수의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 (Base condition)

모든 입력은 base condition으로 수렴해야 함

 

 

재귀에서는 함수를 명확하게 정의해야한다!

- 함수의 인자로 어떤 것을 받을지

- 어디까지 계산한 후 자기 자신에게 넘겨줄지

 

 

모든 재귀 함수는 반복문만으로 동일한 동작하는 함수 만들 수 있음

재귀는 반복문 구현보다 코드가 간결하지만 메모리/시간에서는 손해 -> 적절한 때에 재귀 구현

한 함수가 자기 자신을 여러 번 호출 -> 매우 비효율적!!

 

 

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨 -> 스택 제한이 있는 경우 메모리 초과 날 수 있음

 

 

백준 11729번 (하노이 탑 이동 순서)

import java.awt.*;
import java.util.*;
import java.io.*;


public class Main {

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        sb.append((int)(Math.pow(2, N))-1).append("\n");
        //System.out.println((int)(Math.pow(2, N))-1);
        func(1, 3, N);

        System.out.print(sb);
    }

    private static void func(int start, int end, int n) {
        if(n==1){
            sb.append(start).append(" ").append(end).append("\n");
            //System.out.println(start+" "+end);
            //System.out.println(sb);
            return;
        }
        func(start, 6-start-end, n-1);
        sb.append(start).append(" ").append(end).append("\n");
        func(6-start-end, end, n-1);
    }


}