[JAVA] 재귀

사이드 프로젝트, 자격증 시험과 취준 덕분에 너무 바빠 얼마 하지도 않은 블로깅이 또 뜸해졌다.. 반성 🙏🏻

 

재귀함수

프로그래밍에서는 하나의 함수가 자기 자신을 호출하는 것을 뜻한다.

팩토리얼, 하노이탑, 유클리드 호제법, 조합 문제 등 다양한 방법으로 재귀 함수를 사용하곤 한다.

 

재귀는 이런 상황에 적합하다고 한다.

1. 하나의 문제에서 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
3. 변수 사용을 줄여 mutable state (변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
		for(int k = 0; k < n; k++) {
			for(int l = 0; l < n; l++) {
				for(int m = 0; m < n; m++) {
					function(i, j, k, l, m);
				}
			}
		}
	}
}

으아악

 

---

예제

재귀로 푼 문제는 해당 게시글에 계속해서 추가할 예정

 

▶️ [프로그래머스 Lv.0] 유한소수 판별하기(feat. 유클리드 호제법)

 

class Solution {
    public int solution(int a, int b) {
        int num = b / gcd(a, b);

        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else if (num % 5 == 0) {
                num /= 5;
            } else {
                return 2;
            }
        }
        return 1;
    }
    // 최대공약수 구하기(유클리드 호제법)
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

 

▶️ [프로그래머스 Lv.0] 구슬을 나누는 경우의 수

 

class Solution {
    public int solution(int balls, int share) {
        int answer = combination(balls, share);
        
        return answer;
    }
    
    public int combination(int n, int m) {
        if(m == 0 || n == m) { return 1; }
        else {
            return combination(n-1, m-1) + combination(n-1, m);
        }
    }
}

 

▶️ [프로그래머스 Lv.0] 분수의 덧셈 ( + 04.20 추가 )

 

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        
        // 두 개의 분수 우선 통분
        int numer3 = (denom2 * numer1) + (denom1 * numer2);
        int denom3 = denom1 * denom2;
        
        // 최대공약수로 분자, 분모 나누기(약분)
        answer[0] = numer3 / gcd(numer3, denom3);
        answer[1] = denom3 / gcd(numer3, denom3);
        
        return answer;
    }
    private int gcd(int a, int b) {
        if(b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

 

▶️ [프로그래머스 Lv.1] 최대공약수와 최소공배수 ( + 07.28 추가 )

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        answer[0] = gcd(n, m);
        answer[1] = n * m / gcd(n, m);
        
        return answer;
    }
    private int gcd(int a, int b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
}