참고
재귀(Recursion)
NOTE
재귀 ⇒ 함수 내부에서 자신을 다시 호출하는 기능!
•
대표적으로 정렬, Heap, Tree, Graph에서 사용된다.
•
잘 활용하면 깔끔하게 코드를 작성할 수 있기 때문에 제귀적으로 생각하는 방법을 익히는것이 중요하다.
수학적 귀납법과 재귀
수학적 귀납법 (Mathematical Induction)
NOTE
수학에서 명제가 모든 자연수에 대해 참임을 증명하는 방법 중 하나!
•
자신보다 작은 명제가 참이라고 증명하고, 자신도 따라서 참이라는 것을 보이는 방식
•
증명 방법
1.
가장 작은 자연수 (1, 0)에 대해 명제가 참인지 확인 (기본단계)
2.
어떤 자연수 k에 대해 명제가 참이면, k+1에 대해서도 참일것이다! (귀납단계)
재귀
NOTE
수학적 귀납법과 재귀는 비슷한 논리구조를 가지며, 모든 재귀 알고리즘은 명시적으로 다음 구성요소를 반드시 갖추어야 한다!
1.
경게 조건(Base Case)
•
재귀 알고리즘은 종료 조건이 필요하다.
•
이를 기본 경우(base case)라고 부르며, 이 경우에는 알고리즘이 더 이상 재귀를 호출하지 않는다.
2.
재귀 호출
•
자신 (recursion(K+1)) 보다 작은 문제 (recursion(k))에 대해서 알고리즘이 동작하면 자신도 동작한다.
재귀적 구조를 작고 있는 알고리즘들
등차 수열
NOTE
수학에서 명제가 모든 자연수에 대해 참임을 증명하는 방법 중 하나!
•
자신보다 작은 명제가 참이라고 증명하고, 자신도 따라서 참이라는 것을 보이는 방식
•
증명 방법
1.
가장 작은 자연수 (1, 0)에 대해 명제가 참인지 확인 (기본단계)
2.
어떤 자연수 k에 대해 명제가 참이면, k+1에 대해서도 참일것이다! (귀납단계)
하노이 탑
NOTE
3개의 기둥을 다른 기둥으로 옮기는 알고리즘!
.gif&blockId=e3fea071-6421-4f11-84f8-b034e64e711c)
move(3, a, b, c) {
if ( n > 0 ) {
- move(2, a, c, b) // a에 있는 위에 2개 -> c로 이동 (그림 1-1 참고)
- move(1, a, b, c) // a에 작은 원판 1개 -> b로 이동 (실행 1)
- a -> c 이동 // a에 큰 원판 1개 -> c로 이동 (실행 2)
- move(1, b, c, a) // b에 작은 있는 1개 -> c로 이동 (실행 3)
- a -> b 이동 // 실행 4 (그림 1-2 참고)
- move(2, c, b, a) // c에 있는 2개 -> b로 이동 (그림 1-3 참고)
- move(1, c, a, b) // c에 있는 작은 원판 1개 -> a로 이동 (실행 5)
- c -> b 이동 // c에 큰 원판 1개 -> a로 이동 (실행 6)
- move(1, a, b, c) // a에 작은 원판 1개 -> b로 이동 (실행 완료)
}
}
Java
복사