[Python 기초] 재귀함수 이해하기(피보나치, 최대공약수, 하노이의 탑)

재귀함수는 함수 정의 내 같은 이름의 함수가 올 때 이를 재귀함수라고 하며, 반드시 탈출 조건이 있어야 stack overflow를 방지할 수 있다. 같은 행위가 반복될 때 재귀함수를 사용한다. 재귀함수를 피보나치, 최대공약수, 하노이의 탑의 예제를 통해 이해해 보고자 한다.

 

#피보나치 수열

#for문 사용
def fibo(n):
    list = []
    for i in range(0,n):
        if i<2:
            list.append(1)
        else:
            list.append(list[i-1]+list[i-2])
    return list[n-1]
print(fibo(4)) #3

#재귀 사용
def fibo(n):
    if n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
print(fibo(4)) #3

 

 

#최대공약수(유클리드 호제법)

- 최대 공약수: 두 수를 공통으로 나눌 수 있는 정수 중 가장 큰 것. (예: 12와 16의 최대공약수는 4)

- 최대 공약수: 두 수의 곱을 최대공약수로 나누면 최소공배수가 된다. (예: (12*16)/4=48)

def gcd(m, n):
    if m < n:
        m, n = n, m #큰 순으로 정렬
    if m % n == 0: #큰 수에서 작은 수가 나눠지면
        return n #작은 수가 최대공약수
    else:
        return gcd(n, m%n) #재귀로 반복

print(gcd(48, 60)) # 12

 

 

#하노이의 탑

- 하노이의 탑이란? 

(출처: 위키피디아)

1. 크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥로 전부 옮겨야 한다.

2. 원반은 한 번에 한 개씩만 옮길 수 있다.

2. 원반을 옮길 때는 한 기둥의 맨 위 원반을 빼내어, 다른 기중의 맨 위로만 옮길 수 있다.

4. 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없다.

 

- 하노이의 탑 알고리즘 풀이

1. 원반이 n개 일때, 1번 기둥에 있는 n-1개의 원반을 2번 기둥에 옮긴다.

2. 1번 기둥에 남아 있는 원반 중 가장 큰 원반을 3번으로 옮긴다.

3. 2번 기둥에 있는 n-1원반을 3번 기둥으로 옮긴다.

 

원반이 하나 더 작은 값의 알고리즘을 호출 하여 반복적으로 문제를 해결하는 재귀 호출 알고리즘이다.

#3개의 원반을 1번 기둥에서 3번 기둥으로 옮기는데 2번 기둥을 보조로 쓰겠다.
hanoi(3, 1, 3, 2)

#원반이 1개일 때
def hanoi(원반개수, 시작, 목표, 보조):
	if 원반개수 == 1:
    	print(시작, '->', 목표)
        return


#원반이 2개 이상일 때 
	hanoi(원반개수-1, 시작, 목표, 보조) #맨 아래에 있는 원반을 제외한 모든 원반을 보조 기둥으로 옮김
    print(시작, '->', 목표) #남은 1개를 목표 기둥으로 옮김
	hanoi(원반개수-1, 보조, 목표, 시작) 

 

 

# 하노이의 탑 
# 입력: 옮기려는 원반의 갯수 n 
# 옮길 원반이 현재 있는 출발점 기둥 from_pos 
# 원반을 옮길 도착점 기둥 to_pos 
# 옮기는 과정에서 사용할 보조 기둥 aux_pos 
# 출력: 원반을 옮기는 순서 

def hanoi(n, from_pos, to_pos, aux_pos): 
	if n == 1: # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨 
	print(from_pos, "->", to_pos) 
	return 

	# 원반 n - 1개를 aux_pos로 이동(to_pos를 보조 기둥으로) 
	hanoi(n - 1, from_pos, aux_pos, to_pos) 
	# 가장 큰 원반을 목적지로 이동 
    print(from_pos, "->", to_pos) 
	# aux_pos에 있는 원반 n-1개를 목적지로 이동(from_pos를 보조 기둥으로) 
	hanoi(n - 1, aux_pos, to_pos, from_pos) 
    
print("n = 1")
hanoi(1, 1, 3, 2) # 원반 한 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로) 
print("n = 2") 
hanoi(2, 1, 3, 2) # 원반 두 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로) 
print("n = 3") 
hanoi(3, 1, 3, 2) # 원반 세 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)

 

(참고 사이트)

wayhome25.github.io/cs/2017/04/15/cs-16-1-recursion/

www.youtube.com/watch?v=FYCGV6F1NuY

stricky.tistory.com/155