2. 순환

개요

순환(Recursion)이란,

알고리즘이나 함수(메소드)가 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다.

순환은 독특한 개념적인 프레임 워크를 제공하며, 자료구조를 다루는 프로그램에 적합합니다.

---

재귀 함수

재귀 함수(Recursion Function)은 자기 자신을 호출하는 함수입니다.

재귀 함수는 자신을 반복적으로 호출함으로써, 원하는 결과를 도출해낼 수 있습니다.

 

그러나, 재귀 함수는 여러번 호출하기에 시간 복잡도가 크다는 단점이 있습니다.

보통, 중복되는 계산을 줄이기 위해, 메모이제이션(memoization)을 이용합니다.

메모이제이션은 한 번 계산한 결과를 메모리에 저장하였다가 꺼내서 중복 계산을 방지하는 방식입니다.

---

거듭제곱 계산

p의 n제곱을 구하는 방법은 p를 n번 곱하여 값을 반환하는 것입니다.

Java에서는 pow() 메소드가 제공되지만, 순환을 이용하여 값을 구할 수 있습니다.

 

재귀를 이용할 경우 시간 복잡도는 O(n)입니다.

일반적으로 pow() 메소드의 시간 복잡도가 O(log n)인 것을 비교했을 때,

거듭제곱 계산은 pow() 메소드를 이용하는 것이 효율 측면에서는 좋습니다.

---

하노이 탑

하노이 탑은 3개의 기둥에 적당한 개수의 원반을 쌓아 놓고 다른 쪽으로 옮기는 게임입니다.

하노이 탑은 한 번에 하나의 원반만 옮길 수 있고, 큰 원반을 작은 원반 위에 놓을 수 없다는 규칙이 있습니다.

 

하노이 탑의 기본적인 원리는 n개의 원반 중,

크기가 가장 큰 원반을 제외한 n-1개의 원반을 목표 기둥이 아닌 곳으로 옮기고,

이후, n개의 원반을 목표 기둥으로 옮기는 작업을 반복하는 것입니다.

순환을 통해, 다음과 같이 하노이탑을 구현할 수 있습니다.

 

순환을 이용할 경우 시간 복잡도는 O(2^n)입니다.

하노이 탑은 구현할 때마다 3개의 하위 문제로 분할되기 때문입니다.

---

피보나치 수열

피보나치 수열은 1번째 값을 0, 2번째 값을 1으로 정의하고,

N번째 값부터 N-1번째 값과 N-2번째 값을 더한 수열입니다. (N은 3보다 크거나 같은 자연수입니다.)

 

순환을 이용할 경우 시간 복잡도는 O(2^n)이므로, 위의 코드는 상당히 비효율적인 코드입니다.

각 메소드가 독특한 값을 가지는 하노이 탑과 달리,

피보나치 수열은 항상 같은 값을 가지기 때문에,

메모이제이션을 통해, 시간 복잡도를 줄일 수 있습니다.

 

HashMap은 값을 저장하는 자료구조라고 볼 수 있습니다.

HashMap은 key 테이블과 value 테이블을 가집니다.

 

put(key, value)는 key 테이블에 key를 저장하고,

이에 대응하는 value를 value 테이블에 저장하는 역할을 합니다.

 

containsKey(key)는 해당 key의 이름을 가진 key가 있는지 확인하고,

있다면 true 없으면 false를 반환합니다.

 

get(key)는 해당 key에 대응하는 value를 반환합니다.

 

위의 프로그램을 실행할 경우, 시간 복잡도를 O(n)으로 줄일 수 있습니다.

---

main() 메소드

위 알고리즘의 실행 예시입니다.

 

 

📢 출력 예시
===== 거듭제곱 구하기 =====
1024.0(연산 횟수: 11)
1024.0

======= 하노이 탑 =======
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
3번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
4번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
3번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
5번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
3번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
4번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
3번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
6번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
3번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
4번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
3번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
5번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
3번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
4번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
3번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
7번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
3번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
4번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
3번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
5번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
3번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
4번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
3번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
6번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
3번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
4번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
3번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
5번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
3번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
2번 원반을 3번 기둥에서 1번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
4번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
2번 원반을 1번 기둥에서 2번 기둥으로 옮깁니다.
1번 원반을 3번 기둥에서 2번 기둥으로 옮깁니다.
3번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 2번 기둥에서 1번 기둥으로 옮깁니다.
2번 원반을 2번 기둥에서 3번 기둥으로 옮깁니다.
1번 원반을 1번 기둥에서 3번 기둥으로 옮깁니다.
(연산 횟수: 127)

======= 피보나치 수열 =======
0 1 1 2 3 5 8 13 21 34 (연산 횟수: 276)

== 메모이제이션 피보나치 수열 ==
0 1 1 2 3 5 8 13 21 34 (연산 횟수: 26)

 

시간 복잡도와 연산 횟수는 비례 관계입니다.

---

정리

순환은 코드의 재사용성과 간결성을 높이는데 큰 기여를 하는 프로그래밍 기법이지만, 

연산을 반복적으로 하기 때문에, 코드가 무거워질 수 있다는 단점이 있습니다.

 

순환 기법을 사용할 때는 이를 고려하여서 코딩을 할 필요가 있어 보입니다.

다음에는 '연결 리스트'를 다룹니다.