Recursion: base case and recursive case · 재귀: 기본 조건 및 재귀 조건
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
English
A method that calls itself
- Recursion is when a method calls itself to solve a smaller piece of the same problem.
- On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
- Every recursive method needs two parts: a base case and a recursive case.
한국어
자신을 호출하는 메소드
- 재귀는 같은 문제의 더 작은 부분을 해결하기 위해 메소드가 자신을 호출하는 것입니다.
- AP CSA 시험에서는 주로 재귀를 추적합니다(손으로 호출을 따름). 작은 재귀 메소드를 작성하면 추적을 잘 할 수 있습니다.
- 모든 재귀 메소드는 두 부분이 필요합니다: **기저 사례(base case)**와 재귀 사례(recursive case).
English
Base case and recursive case
- Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
- Recursive case: you call the same method with a smaller input, then build the answer.
- Without a base case, the method calls forever and crashes (a stack overflow).
한국어
기본 경우와 재귀 경우
- 기저 사례: 가장 간단한 입력으로, 자신을 호출하지 않고 답을 반환하는 지점입니다.これで recursion을 멈춥니다.
- 재귀 사례: 더 작은 입력으로 동일한 메소드를 호출한 뒤 답을 구성합니다.
- 기저 사례가 없으면 메소드가 영원히 자신을 호출하여 충돌/스택 오버플로우가 발생합니다.
English
Example: factorial
factorial(n)meansn * (n-1) * ... * 1. For examplefactorial(4) = 24.- Base case:
factorial(1)is1. - Recursive case:
factorial(n)isn * factorial(n - 1).
한국어
예제: 계승(factorial)
factorial(n)은n * (n-1) * ... * 1을 의미합니다. 예를 들어factorial(4) = 24.- 기저 사례:
factorial(1)는1입니다. - 재귀적 경우:
factorial(n)은n * factorial(n - 1)입니다.
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
English
How the calls unwind
- Each call waits for the smaller call to finish. Then it multiplies and returns.
- Trace
factorial(3). Calls go down, then answers come back up.
한국어
호출이 undone되는 방식
- 각 호출은 더 작은 호출이 완료될 때까지 대기합니다. 그런 다음 곱하여 반환합니다.
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
English
Example: sum to n
sumTo(n)adds1 + 2 + ... + n. For examplesumTo(4) = 10.- Base case:
sumTo(0)is0(nothing to add). - Recursive case:
sumTo(n)isn + sumTo(n - 1).
한국어
예제: n까지의 합계
sumTo(n)에1 + 2 + ... + n을 더합니다. 예를 들어sumTo(4) = 10인 경우를 생각할 수 있습니다.- 기본 경우:
sumTo(0)은0이며(더 할 것이 없음) 바로 반환합니다. - 재귀적 경우:
sumTo(n)은n + sumTo(n - 1)입니다.
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
English
Recursion over an array
- We can also recurse with an index that moves toward the end.
- Base case: when the index is past the last spot, return
0. - Recursive case: add
a[i]to the sum of the rest,arraySum(a, i + 1).
한국어
배열에 대한 재귀
- 끝으로 향하는 인덱스를 사용하여 재귀를 수행할 수도 있습니다.
- 기본 경우: 인덱스가 마지막 위치를 넘었을 때,
0을 반환합니다. - 재귀적 경우:
a[i]을 나머지 부분의 합인arraySum(a, i + 1)에 더합니다.
English
- To sum the whole array you start at index
0:arraySum(a, 0). - Each call handles one value and trusts the next call for the rest.
한국어
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). - 각 호출은 하나의 값만 처리하고 나머지는 다음 호출에 맡깁니다.
English
Common mistakes
- Recursion needs a base case, or it throws StackOverflowError.
- Each call must move closer to the base case.
한국어
흔한 실수
- 재귀에는 기본 경우가 필요합니다. 그렇지 않으면 StackOverflowError가 발생합니다.
- 각 호출은 반드시 기본 경우에 가까워져야 합니다.
English
Now you try
- Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
- A hidden Harness calls your method with several values and checks the result.
- Press Run to compile, then Check answer.
한국어
이제 직접 해보기
- 각 과제는 TODO가 포함된 메소드 골격을 제공합니다. 기본 경우와 재귀적 경우를 모두 작성하십시오.
- 숨겨진 Harness가 여러 값을 사용하여 해당 메소드를 호출하고 결과를 확인합니다.
- 컴파일하려면 Run을 누르고, 그 후 Check answer를 누르십시오.
Explore · 탐색하기
Recursion: base + recursive case · 재귀: 기본 + 재귀 조건
Calls split until a base case, then answers return up. · 기본 조건까지 분할한 뒤, 답이 위로 돌아옵니다.
Complete factorial(int n) so it returns n * (n-1) * ... * 1 using recursion. Use a base case for n <= 1. The checker tests several values. · factorial(int n)를 완성하여 n * (n-1) * ... * 1를 재귀로 반환하게 하세요. n <= 1에 대한 기본 조건을 사용하세요. 체크 프로그램은 여러 값으로 테스트합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete sumTo(int n) so it returns 1 + 2 + ... + n using recursion. Use a base case for n <= 0. The checker tests several values. · sumTo(int n)를 완성하여 1 + 2 + ... + n를 재귀로 반환하게 하세요. n <= 0에 대한 기본 조건을 사용하세요. 체크 프로그램은 여러 값으로 테스트합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete arraySum(int[] a, int i) so it returns the sum of a[i] to the end, using recursion. Base case: when i is past the last spot, return 0. The checker tests several arrays. · arraySum(int[] a, int i)을 완성하여 a[i]부터 끝까지의 합을 재귀로 반환하도록 하십시오. 기본 사례: i가 마지막 위치를 넘었을 때 0을 반환합니다. 체크기는 여러 배열을 테스트합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.