[자료구조] 02. 재귀

포스팅을 시작하기 전에

 

생각보다 글 쓰는게 빡세다.. (그림파일도)

방학 전까지 포스팅 완료하고 싶다 ㅠㅠㅠㅠ

 

 

 

---

키워드

 

#실행시간 #의사코드 #재귀

 

---

1. 재귀 (recursive)

정의 단계에서 자신을 재참조하는 알고리즘을 재귀적이라고 한다.

 

Alg sum(n)
	if (n = 1)
    	return 1
    else
    	return n + sum(n-1)

1부터 n까지의 합을 구하는 함수

재귀함수는 두 가지 부분으로 나눌 수 있는데,

• 재귀 케이스 (recursion)

함수 자기 자신을 호출하는 부분. 차후의 재귀 호출은 작아진 부분 문제(subproblems)를 가지고 작동함

 

• 베이스 케이스 (base case)

재귀함수 탈출 조건. 베이스 케이스가 존재해야 재귀 함수 동작을 끝낼 수 있다!

 

그렇다면 위 alg sum에서의 base case, recursion 부분은 어디일까?

n == 1일 때 재귀호출이 끝나므로 다음과 같다

 

return 1 // base case

return n + sum(n-1) // recursion

 

동작 과정

 

[그림1] 콜스택

 

차곡차곡 콜스택에 함수가 쌓이다가, base case 조건에 도달하면 콜스택에서 함수가 하나씩 수행되며 사라진다.

따라서 재귀호출은 항상 base case를 향하는 방향으로 진행되어야 한다.

 

 

재귀함수의 장단점

장점

• 재귀적 호출로 현재 상태를 변경, 저장, 전달이 가능하기에 변수의 수를 줄일 수 있음
• 반복문을 사용하지 않아도 되어 코드가 간결하고 이해하기 쉬움
• 특히 재귀 호출이 적합한 상황 (팩토리얼, 피보나치) 에서 사용할 경우 깔끔하게 코드 작성 가능

재귀 호출이 적합한 상황인지는 어떻게 알아?

후에 나올 분할 정복(divide and conquer)이라는 개념과 관련이 있다.
간략하게 설명하면 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.
재귀 호출을 실행하며 작아진 부분문제를 가지고 작동하는 방법으로, 알고리즘 포스팅에서 재귀 뿐만 아니라 스택, 큐 등으로 이를 해결하는 방법도 설명할 예정이다. 

단점

• 함수 호출 시 스택에 저장하면서 메모리를 많이 사용하게 되고 속도 저하
• 함수 호출 및 복귀를 위한 컨텍스트 스위칭 비용 발생 (컴퓨터 구조에서 관련 내용 나옴)

 

여러 가지 문제를 풀어보면서 재귀함수 구현을 익혀보는 연습이 필요하다!

 

재귀함수 응용

 

손풀기(?)로 간단한 문제부터 풀어보자.

 

1. 재귀적 곱하기와 나누기

• a와 b의 곱을 계산하는 재귀 알고리즘 product(a,b)를 작성하라.

Alg product(a,b)
// input : positive integer a,b
// output : product of a and b

if (b=1) // base case
	return a
else // recursion
	return a + product(a, b-1)

# python 구현
def product(a,b):
    if a == 0:
        return b
    else:
        return product(a-1, b+a)

print(product(2,3)) # 출력값 : 6

• a를 b로 나눈 나머지를 계산하는 재귀 알고리즘 modulo(a,b)를 작성하라.

Alg modulo(a,b)
// input : positive integer a,b
// output : a % b

if (a < b) // base case
	return a
else
	return modulo(a-b, b) // recursion

# python 구현
def modulo(a,b):
    if a<b:
        return a
    else:
        return modulo(a-b, b)

print(modulo(5,3)) # 출력값 : 2

• a를 b로 나눈 몫을 계산하는 재귀 알고리즘 quotient(a,b)를 작성하라.

Alg quotient(a,b)
// input : positive integer a, b
// output : a/b

if (a < b)
	return 0
else
	return 1 + quotient(a-b, b)

# python 구현
def quotient(a,b):
    if a<b:
        return 0
    else:
        return 1 + quotient(a-b, b)

print(quotient(5,3)) # 출력값 : 1

 

 

2. 하노이탑

하노이탑 문제 - 재귀 알고리즘을 설명할 때 가장 많이 쓰이는 문제이다!

 

세 개의 말뚝 A, B, C가 존재할 때 직경이 다른 n (n은 양의 정수) 개의 원반이 A에 쌓여있다. 
이 때 모든 원반을 말뚝 A에서 C로 옮기는 문제이다.
단, 원반 이동 과정에서 아래의 조건들을 만족해야 한다.

<조건>
1. 한 번에 한 개의 원반만을 이동시킬 수 있다.
2. 어느 시점에서도 직경이 큰 원반이 작은 원반 위에 놓일 수 없다.
3. 남아있는 하나의 말뚝은 보조 말뚝으로 사용 가능하다.

 

풀이과정을 보기 전 잠시 멈춰서 생각해보자..

 

---

 

 

풀이과정

 

문제를 세부적으로 나누어서 풀어보자.

(설명 편의상 원반은 위에서부터 1~n으로 지칭한다)

 

1. 원반이 1개일 때

 

이 경우는 매우 간단하다. 그냥 A의 원반 1을 목표 지점인 C로 바로 옮기면 된다!

 

 

 

 

2. 원반이 2개일 때

여기서부터 보조말뚝 (B) 가 사용된다.

원반을 한번에 옮길 수 없으므로

1. B에 원반 1을 옮겨둔다
2. C에 원반 2를 옮긴다
3. B에 옮겨 놓았던 원반 1을 C로 옮긴다

 

 

 

3. 원반이 3개일 때

 

문제를 크게 분석하면 풀이 과정은 다음과 같다.

1. 원반 1,2 를 보조말뚝 B에 옮겨놓는다
2. 원반 3을 C로 옮긴다
3. 보조말뚝 B의 원반 2개를 다시 C로 옮긴다

그리고 과정 1, 3은 원반이 2개일 때 옮기는 과정으로 풀 수 있다.

 

즉, 이 문제는 재귀함수를 통해 해결할 수 있는 문제이다!

 

 

 

 

 

원반이 3개보다 많을 때도 비슷하게 풀 수 있다.

 

4. 원반이 4개일 때

1. 원반 1,2,3을 보조말뚝 B에 옮겨놓는다
2. 원반 4를 B로 옮긴다
3. 보조말뚝 B의 원반 3개를 다시 C로 옮긴다

 

과정이 많은 것 같지만 일반화하면 간단하다!

위의 예시들을 바탕으로 규칙을 찾아내면,

• 1~n-1번 원반을 보조말뚝에 옮긴다
• n번 원반을 목적지에 옮긴다
• 1~n-1번 원반을 목적지에 옮기는 문제를 재귀적으로 푼다

재귀를 수행하며 하위 문제로 나누어지고, 마침내 base case(n=1) 에 도달하는 과정을 확인할 수 있다

이는 초반 재귀의 정의와 동작과정에서 다루었던 부분이다. 위로 올라가서 다시 확인해보자!

 

또한 일반화 규칙을 통해 원반을 총 몇 번 움직여야하는지 구할 수 있다.

• n=1일 때, (2^1 -1 = 1)
• n=2일 때, (2^2 - 1 = 3)
• n=3일 때, (2^3 -1 = 7)
• n=4일 때, (2^4 - 1 = 15)

따라서 원반의 개수가 n일 때, 목적지 말뚝으로 옮기기 위해 필요한 총 이동 횟수는 2^n -1이다.

 

https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/e/move-three-disks-in-towers-of-hanoi

 

이곳에서 직접 원반을 옮겨보며 연습해보는 것도 이해에 도움이 될 듯 하다

 

 

의사코드 구현

 

이제 하노이 탑을 어떻게 풀 지 감이 잡혔으니, 직접 구현해볼 일만 남았다.

의사코드부터 작성해보자!

 

Alg hanoi(n)
	rHanoi(n, 'A', 'B', 'C')
    return

원반의 개수를 전달받으면 재귀함수 rHanoi를 호출하는 함수이다.

왜 굳이 Hanoi와 rHanoi 함수 2개로 나눠서 썼을까?

사실 rHanoi만 있어도 목표 달성은 가능하다.
하지만 main함수에서 하노이함수를 사용할 때 보다 깔끔하게 원반 개수만 전달할 수 있도록 (말뚝 이름은 이미 정해져있다는 전제 하에) hanoi와 rHanoi로 나누어 구현했다.

 

/* n : 이동해야 할 원반 수
   from : 출발 말뚝
   aux : 보조말뚝
   to : 목표말뚝
*/

Alg rHanoi(n, from, aux, to)
	if (n=1) // base case (종료조건)
    	// 원반 이동과정 출력
    	print("move from", from, "to", to)
        return
    rHanoi(n-1, from, to, aux) // 1~n-1 번 원반을 보조말뚝으로 옮김
    print("move from", from, "to", to) // n번 원반을 목적지로 옮김
    rHanoi(n-1, aux, from, to) // 1~n-1번 원반을 목적지로 옮김
    return

 

 

파이썬 구현

 

의사코드를 바탕으로 파이썬에 구현한 내용이다.

def hanoi(n):
    # 'A' : from (시작 말뚝), 'B' : aux (보조말뚝), 'C' : to (목적지 말뚝)
    rHanoi(n, 'A', 'B', 'C')
    return 

def rHanoi(n, fr, aux, to):

    # base case
    if n == 1:
        print("move from", fr, "to", to)
        return
    
    # recursive
    rHanoi(n-1, fr, to, aux) # 1~n-1번 원반을 보조말뚝으로 
    print("move from", fr, "to", to) # n번 원반을 목적지 말뚝으로
    rHanoi(n-1, aux, fr, to) # 1~n-1번 원반을 목적지 말뚝으로
    return


n = int(input("원반의 개수를 입력하세요 : "))
hanoi(n)
print("#### 출력 종료 ####")

 

 

2. 재귀 활용

위에서 살펴본 하노이탑 예제와 같이, 재귀로 풀어야 깔끔하게 풀리는 문제들이 있다.

백준에서 문제 예시 몇 개를 가져왔다

 

(문제들 풀이는 추후 포스팅에서 다룰 예정)

 

 

• 팩토리얼 : https://www.acmicpc.net/problem/10872

10872번: 팩토리얼

 

• 피보나치 수열 : https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

• 하노이 탑 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

• 기타 재귀 문제 : https://www.acmicpc.net/problemset?sort=ac_desc&algo=62

문제 - 1 페이지