이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
자신을 호출하는 메소드
- 재귀는 같은 문제의 더 작은 부분을 해결하기 위해 메소드가 자신을 호출하는 것입니다.
- AP CSA 시험에서는 주로 재귀를 추적합니다(손으로 호출을 따름). 작은 재귀 메소드를 작성하면 추적을 잘 할 수 있습니다.
- 모든 재귀 메소드는 두 부분이 필요합니다: **기저 사례(base case)**와 재귀 사례(recursive case).
기본 경우와 재귀 경우
- 기본 조건(base case): 가장 간단한 입력으로, 자신을 호출하지 않고 답을 반환합니다. 이것이 재귀를 멈춥니다.
- 재귀 사례: 더 작은 입력으로 동일한 메소드를 호출한 뒤 답을 구성합니다.
- 기저 사례가 없으면 메소드가 영원히 자신을 호출하여 충돌/스택 오버플로우가 발생합니다.
예제: 계승(factorial)
factorial(n)은n * (n-1) * ... * 1을 의미합니다. 예를 들어factorial(4) = 24.- 기저 사례:
factorial(1)는1입니다. - 재귀적 경우:
factorial(n)은n * factorial(n - 1)입니다.
English
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
호출이 풀리는 방식
- 각 호출은 더 작은 호출이 완료될 때까지 대기합니다. 그런 다음 곱하여 반환합니다.
factorial(3)을 추적해 보십시오. 호출은 아래로 내려가고, 답변은 위로 돌아옵니다.
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
예제: n까지의 합계
sumTo(n)에1 + 2 + ... + n을 더합니다. 예를 들어sumTo(4) = 10인 경우를 생각할 수 있습니다.- 기본 경우:
sumTo(0)은0이며(더 할 것이 없음) 바로 반환합니다. - 재귀적 경우:
sumTo(n)은n + sumTo(n - 1)입니다.
English
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
배열에 대한 재귀
- 끝으로 향하는 인덱스를 사용하여 재귀를 수행할 수도 있습니다.
- 기본 경우: 인덱스가 마지막 위치를 넘었을 때,
0을 반환합니다. - 재귀적 경우:
a[i]을 나머지 부분의 합인arraySum(a, i + 1)에 더합니다.
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- 전체 배열의 합계를 구하려면 인덱스
0에서 시작합니다:arraySum(a, 0). - 각 호출은 하나의 값만 처리하고 나머지는 다음 호출에 맡깁니다.
흔한 실수
- 재귀에는 기본 경우가 필요합니다. 그렇지 않으면 StackOverflowError가 발생합니다.
- 각 호출은 반드시 기본 경우에 가까워져야 합니다.
이제 직접 해보기
- 각 과제는 TODO가 포함된 메소드 골격을 제공합니다. 기본 경우와 재귀적 경우를 모두 작성하십시오.
- 숨겨진 Harness가 여러 값을 사용하여 해당 메소드를 호출하고 결과를 확인합니다.
- Check answer를 사용하여 제공된 테스트와 함께 코드를 컴파일하고 결과를 확인하십시오. 시작 파일에 표시된 클래스 및 메서드 인터페이스를 유지하십시오.
탐색하기
재귀: 기본 + 재귀 조건
기본 조건까지 분할한 뒤, 답이 위로 돌아옵니다.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
factorial(int n)를 완성하여 n * (n-1) * ... * 1를 재귀로 반환하게 하세요. n <= 1에 대한 기본 조건을 사용하세요. 체크 프로그램은 여러 값으로 테스트합니다.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
sumTo(int n)를 완성하여 1 + 2 + ... + n를 재귀로 반환하게 하세요. n <= 0에 대한 기본 조건을 사용하세요. 체크 프로그램은 여러 값으로 테스트합니다.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
arraySum(int[] a, int i)을 완성하여 a[i]부터 끝까지의 합을 재귀로 반환하도록 하십시오. 기본 사례: i가 마지막 위치를 넘었을 때 0을 반환합니다. 체크기는 여러 배열을 테스트합니다.
출력을 보려면 '실행'을 클릭하세요.