[JAVA] 쉽게 이해하는 재귀함수

결론

1. 재귀함수는 큰 단위의 일을 작은 단위로 쪼개서 일을 시키는 것이다.

2. 재귀함수는 순열/조합, DFS에서 자주 사용된다.

3. 재귀함수는 종료 조건과 점화식/쪼갠 일의 task을 구하면 된다.

재귀 함수의 이해

재귀 함수는 자기 자신을 또 부르는 함수이다.

만약 아래와 같은 코드가 있다면 어떤식으로 동작할까?

public static void add(int n) {
	add(n-1);
}

 

처음에 add(4) 함수를 호출한다고 가정해보자.

그러면 add(4)는 함수 내부에서 add(3) 를 호출 할 것이다.

add(3)는 또 add(2)을 호출하고,

add(2)는 또 add(1)을 호출할 것이다.

 

이렇게 계속 진행되면 끝없이 add 함수를 호출하고 결국에는 stackoverflow 오류가 나게 된다.

 

그래서 우리는 이 함수가 정상적으로 끝날 수 있도록 종료 조건을 주어야 한다.

만약에 add(0) 까지 호출하고 종료하고 싶다면 아래와 같이 조건문을 추가해주면 된다.

public static void add(int n) {
	if(n==0) return;
	add(n-1);
}

 

만약 위 코드에서 add(2)를 호출하면, add(n-1) 구문에서 add(1)을 호출할 것이고,

add(1) 함수에서 add(n-1) 구문을 통해 add(0)을 호출할 것이다.

add(0)은 n이 0인 경우이므로 return 되고,

다시 연어처럼 거슬러 올라가면서 add(1) 함수에서 멈췄던 구문을 수행하고 마치면 add(2) 함수에서 멈췄던 구문을 수행하고 함수구문을 종료하게 된다.

 

만약 코드의 순서가 아래와 같이 바뀌면 어떻게 될까?

public static void add(int n) {
	add(n-1);
	if(n==0) return;
}

함수는 위에서부터 아래로 순차적으로 구문을 수행한다.

따라서 add(n-1) 구문을 수행하고 if 조건문을 수행한다.

 

add(2) 함수에서 add(1) 함수를 호출하고,

add(1) 함수에서 add(0) 함수를 호출한다.

add(0) 함수에서는 add(n-1) 구문이 우선이므로 add(-1) 함수를 호출한다.

 

if 조건문까지 도달하지 못하므로, 이 경우에도 끝없이 add 함수를 호출되고 결국에는 stackoverflow 오류가 나게 된다.

 

유형1. 점화식이 주어진 경우

팩토리얼은 1~n까지 곱하는 수이다.

5! 를 구한다고 가정했을 때, 아래와 같은 규칙으로 구할 수 있다.

5! = 4! * 5
4! = 3! * 4
3! = 2! * 3
2! = 1! * 2

 

그리고 1!과 0!은 1임이 자명하므로,

종료 조건은 0!과 1!인 경우 값이 1 이라는 것이고,

점화식은 n! = (n-1)! * n 이라는 것이다.

즉, fact(n) = fact(n-1) * n 이다.

 

이를 코드로 나타내면 다음과 같다.

public static int fact(int n) {
	// 종료 조건
    if(n==0 || n==1) return 1;
    
    // 점화식
    return fact(n-1)*n;
}

 

 

유형2. 큰 task를 작은 task로 쪼개야 하는 경우

여러 개의 값에 대해 최소공배수를 구해야 하는 문제가 있다.

예를 들어 4 8 3 9 2 5 의 최소공배수를 어떻게 구할까?

 

여기서 큰 문제는 4 8 3 9 2 5 의 최소공배수를 구하는 것이다.

이를 작은 문제로 쪼개면 아래와 같이 1개씩 최소공배수를 누적해서 구해주면 된다.

f(4 8 3 9 2 5 의 최소공배수)

초기 수 = 1

f(4 8 3 9 2 5의 최소공배수) = f(4 8 3 9 2의 최소공배수) * (기존 수와 5의 최소공배수)
f(4 8 3 9 2의 최소공배수) = f(4 8 3 9의 최소공배수) * (기존 수와 2의 최소공배수)
f(4 8 3 9의 최소공배수) = f(4 8 3의 최소공배수) * (기존 수와 9의 최소공배수)
f(4 8 3의 최소공배수) = f(4 8의 최소공배수) * (기존 수와 3의 최소공배수)
f(4 8의 최소공배수) = f(4의 최소공배수) * (기존 수와 8의 최소공배수)
f(4의 최소공배수) = 기존 수와 4의 최소공배수 // 종료 조건 (더 이상 구할 것이 없음)

 

이를 전체 코드로 나타내면 아래와 같다.

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

public class Main {
    static ArrayList<Integer> numList = new ArrayList<>();
    static int n;
    static long ans = 1;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input, " ");
        for(int i=0; i<n; i++) {
            numList.add(Integer.parseInt(st.nextToken()));
        }

        // logic // 
        multlcd(n-1);
        
        // output //
        bw.write(ans+"");
        bw.flush();
        bw.close();
    }

    // 최대공약수
    public static long gcd(long a, long b) {
        if(b == 0) return a;
        
        return gcd(b,a%b);
    }
    // 최소공배수
    public static long lcd(long a, long b) {
        return a*b/gcd(a,b); 
    }

    // 큰 문제 : n개의 수 최소 공배수를 구한다.
    // 작은 문제로 해결 : 특정 2개의 수를 최소 공배수를 구한다.
    //Ex) f(1,5,7,9,2,6의 최소공배수) = 1과 f(5,7,9,2,6의 최소공배수)
        // = 1과 5의 최소공배수값(7)과 f(7,9,2,6의 최소공배수)
        // = 1,5,7의 최소공배수값(35) 와 f(9,2,6의 최소공배수)
    public static void multlcd(int idx) {
        if(idx==-1) return;

        ans = lcd(ans, numList.get(idx));
        multlcd(idx-1);
    }
}