728x90
Recursion
- 자기 자신을 호출하는 함수
void func(...)
{
func(...);
}
위 함수를 실행코드로 짜보자
public class Recursive1 {
public static void main(String[] args) {
func();
}
public static void func(int k) {
System.out.println("Hello");
func();
}
}
위와 같은 코드를 실행하게 되면 return문이 없기 때문에 무한 반복으로 Hello를 출력하면서 에러가 발생하게 된다.
그럼 Recursion은 항상 무한루프에 빠질까?
그건 아니다.
또 하나의 코드를 보자
public class Code02 {
public static void main(String[] args) {
int k = 4;
func(k);
}
public static void func(int k) {
if (k<=0) // Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
return;
else {
System.out.println("Hello...");
func(k-1); // Recursive case : recursion을 반복하다보면 결국 base case로 수렴해야 한다.
}
}
}
해당 코드는 func 함수에 k의 값을 1을 빼면서 재귀를 하기 때문에 k <= 0일때 return을 통해서 코드를 빠져나오게 된다.
순환함수와 수학적 귀납법
정리 : funcintn은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바로 계산한다.
증명:
1. n=0인 경우: n=0인 경우 0을 반환한다. 올바르다.
2. 임의의 양의 정수 k에 대해서 n<k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정하자.
3. n=k인 경우를 고려해보자. func은 먼저 funck−1 호출하는데 2번의 가정에 의해서 0에서 k-1까지의 합이 올바로 계산되어 반환된다.
메서드 func은 그 값에 n을 더해서 반환한다. 따라서 메서드 func은 0에서 k까지의 합을 올바로 계산하여 반환한다.
0! = 1
n! = n X n−1! n>0
728x90
반응형
'python > algorithm' 카테고리의 다른 글
[백준 2042번] 구간 합 구하기 0 | 2025.05.21 |
---|---|
[백준 11866번] 요세푸스 문제 0 - 큐 0 | 2025.05.20 |
[백준 10866번] 덱 – 덱 자료구조 구현 0 | 2025.05.19 |
백준 11660 구간 합 구하기 5 python 1 | 2024.03.06 |
백준 11399 ATM 문제 풀이 python 1 | 2023.11.27 |