[스터디 과제] 2.재귀 과제

1. 문제

• 재귀를 사용해서 아래의 조건에 부합하는 코드를 작성하세요
• 주어진 숫자의 각 자릿수의 합을 계산하는 코드를 완성해 주세요
  • ex) 1234 → 1 + 2 + 3 + 4 → 10
  • ex2) 1 → 1 → 1\
• 별도의 메서드를 구현할 필요는 없으면 solution 메서드에 대한 재귀만을 사용해서 풀어주세요

---

2. 재귀 개념

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법이다.

특정 조건에서 자기 자신을 계속 호출하다가, 종료 조건(Base Case)을 만나면 더 이상 호출하지 않고 결과를 반환하며 호출 스택을 역순으로 정리해 나가는 방식이다. 

 

재귀를 사용하는 경우 :

1. 문제를 더 작은 하위 문제로 쪼갤 수 있을 때.

2. 하위 문제의 풀이가 동일한 논리로 처리될 수 있을 때.

 

예를 들어, 숫자 1234의 자릿수 합을 구할 때:

맨 끝짜리 숫자 4와 나머지 숫자 123의 합으로 문제를 분할.

숫자 123은 다시 3과 12로 분할.

이렇게 계속 나눠서 1이 남을 때 종료

---

public class Assignment02 {
    public static void main(String[] args) {
        int tc1 = 1324;
        int tc2 = 1118;
        int tc3 = 1;
        int tc4 = 123456789;

        System.out.println(solution(tc1)); // 10
        System.out.println(solution(tc2)); // 11
        System.out.println(solution(tc3)); // 1
        System.out.println(solution(tc4)); // 45
    }

    public static int solution(int num) {
		    //종료 조건 : 숫자가 한 자리수이면 그대로 반환
            if (num < 10) {
               return num;
            }
            // 재귀 호출 : 마지막 자리 숫자(num % 10)를 더하고 나머지 숫자(num / 10)에 대해 solution 호출
            return (num % 10) + solution(num/10)
    }
}

 

return (num % 10) + solution(num / 10);가 누적해서 더해지는 이유 :

재귀 호출의 동작 방식과 관련이 있다.
이 동작은 함수 호출이 쌓이는 호출 스택(Call Stack)을 통해 이루어진다.
재귀는 자신을 호출하면서 계산의 일부를 스택에 남기고, 
모든 호출이 종료되면 스택을 따라 올라오면서 결과를 차례대로 계산한다. 

 

1. 함수의 역할 :

return (num % 10) + solution(num / 10);

num % 10은 현재 숫자의 마지막 자리를 추출한다.

solution(num / 10)은 나머지 숫자를 처리하기 위해 재귀적으로 호출한다.

즉, solution함수는 현재 자의의 숫자를 반환하고, 나머지 자리의 숫자 합을 다시 자기 자신을 호출해서 계산하도록 구성되었다. 

---

실행 과정

 

첫 호출: solution(1324)

• 계산: (1324 % 10) + solution(1324 / 10)

• 1324 % 10 = 4

• solution(1324 / 10) → solution(132)

 대기 상태 :4 + solution(132)

 

두 번째 호출: solution(132)

• 계산: (132 % 10) + solution(132 / 10)

• 132 % 10 = 2

• solution(132 / 10) → solution(13)

• 대기 상태: 2 + solution(13)

 

세 번째 호출: solution(13)

• 계산: (13 % 10) + solution(13 / 10)

• 13 % 10 = 3

• solution(13 / 10) → solution(1)

• 대기 상태: 3 + solution(1)

 

네 번째 호출: solution(1)

• 종료 조건: num < 10이므로 return 1.

---

호출 스택과 계산 순서

 

이제 스택을 따라 올라가면서 각 호출에서 계산이 이루어진다.

1. solution(1) 반환값: 1

• 이전 호출로 돌아감 (solution(13)의 대기 상태).

• 3 + 1 = 4

2. solution(13) 반환값: 4

• 이전 호출로 돌아감 (solution(132)의 대기 상태).

• 2 + 4 = 6

3. solution(132) 반환값: 6

• 이전 호출로 돌아감 (solution(1324)의 대기 상태).

• 4 + 6 = 10

4. solution(1324) 반환값: 10

• 최종 결과.

 

---

왜 누적해서 더해지는가?

 

재귀는 계산을 스택에 쌓아두고 마지막 호출부터 차례로 계산을 완료한다.

• 각 호출은 자신의 현재 자리수를 계산하고, 다음 자리수의 합을 계산하도록 자신을 호출한다.

• 모든 호출이 종료되면 결과가 스택에서 차례로 반환되어 합산된다.

---

호출 스택이 쌓이는 상태 :

1. solution(1324): 계산 중단 → 4 + solution(132)
2. solution(132):  계산 중단 → 2 + solution(13)
3. solution(13):   계산 중단 → 3 + solution(1)
4. solution(1):    종료 조건 → 반환 1

 

반환과정 :

1. solution(1) → 1
2. solution(13) → 3 + 1 = 4
3. solution(132) → 2 + 4 = 6
4. solution(1324) → 4 + 6 = 10

 

---

핵심 요약
1. solution(num / 10)은 더 작은 문제를 해결하려고 자기 자신을 호출한다.
2. 모든 호출이 종료된 뒤, 스택에 저장된 계산들이 역순으로 풀리며 최종 합이 계산된다.
3. 재귀는 각 호출의 결과를 차례대로 누적하는 구조 덕분에 반복문 없이도 합산을 구현할 수 있다.

2024.12.16 - [Java Algorithm Coding Test] - [Java] 재귀 함수와 스택(Stack)의 개념

[Java] 재귀 함수와 스택(Stack)의 개념

2024.12.16 - [Java Algorithm Coding Test] - [Java] 팩토리얼 개념과 코드로 풀어내는 두가지 방법

[Java] 팩토리얼 개념과 코드로 풀어내는 두가지 방법

2024.12.17 - [Java Algorithm Coding Test] - [Java] 유클리드 호제법은 주로 최대공약수(GCD)와 최소공배수(LCM)을 구하는 유형에 쓰인다.

[Java] 유클리드 호제법은 주로 최대공약수(GCD)와 최소공배수(LCM)을 구하는 유형에 쓰인다.