[python] 재귀함수 파헤치기

코딩테스트를 위해서는 알고리즘과 자료구조 공부가 필수적이라고 생각해 알고리즘 공부를 하고 있다.

여러 내용들 중에도 재귀함수가 은근 헷갈리고 어렵게 다가와 복습 겸 정리해보려고 한다.

 

우선 공부에 활용한 도서는 '모두의 알고리즘 with 파이썬'으로

'더북' 사이트에서는 각 챕터별로 내용이 요약되어 있어 해당 사이트를 활용하고 있다. 

 https://thebook.io/006935/ 

더북(TheBook): 모두의 알고리즘 with 파이썬

---

재귀함수 ?

우선 재귀함수란 함수가 자기 자신을 다시 호출하는 것을 뜻하는 함수이다.

가장 기본적인 예시로

def hello():
	print('hello')
    hello() ## 함수 다시 호출
hello()

좋지 않은 예시이기는 하지만 이를 출력하면 'hello'가 무한히 출력된다. 

따라서 재귀 호출 프로그램이 정상적으로 작동하기 위해서는 종료 조건이 필요하다!

---

팩토리얼 계산하기

1) 반복문 활용

n = int(input())
s = 1
for i in range(1,n+1):
	s *= i
print(s)

사실 코딩테스트를 풀면서 for문을 밥먹듯이 적용하기에,,

재귀함수를 사용하는 것보다 반복문을 활용하는 것이 더 편하게 다가오기는 한다.

 

2) 재귀함수 활용

def fact(n):
	if n<=1:
    	return 1 ## 종료조건
    return n * fact(n-1)
print(fact(5))

만일 입력된 n이 1이하인 경우 바로 1이 반환되도록 종료조건을 걸어둔다.

n이 1이 아닌경우 n보다 1씩 작아지며 곱해주어야 하기 때문에 n * fact(n-1)을 활용한다.

그러면  n-1, n-2, n-3,,, 을 반복하며 1이 되는 경우 종료된다. 

즉 5 * 4 * 3 * 2 와 같이 팩토리얼 공식을 따라 곱해지는 것이다.

---

재귀함수를 활용하여 1부터 n까지 합 구하기

def sum_n(n):
	if n==1: ## 종료조건
    	return 1
    return n + sum_n(n-1)
print(sum_n(4))

앞선 팩토리얼 공식과 마찬가지로 n에 n-1, n-2, n-3,,, 이 더해지게 되고

1이 되는 경우 종료되게 된다.

---

최대공약수 구하기

1) 반복문 활용

a,b = 81,27
gcd = []
for i in range(1, max(a,b)):
	if (a%i==0) & (b%i==0):
    		gcd.append(i)
print(max(gcd))

2) 유클리드를 활용한 최대공약수 구하기

유클리드는 a와 b의 최대공약수는 -> b와 a%b의 최대공약수와 같다는 공식을 활용하는 것이다.

def gcd(a,b):
	if b==0: ##정지규칙은 어떤 수와 0의 최대공약수는 자기자신이라는 성질 활용
    	    return a
    return gcd(b,a%b)

a%b의 값이 다시 b로 적용되면서 반복되는 구조이다.

결과적으로 나머지가 0이 되었을 때 정지되어 최대공약수가 출력된다.

---

재귀함수를 활용한 피보나치 수열 만들기

피보나치 수열이란 바로 앞의 두 수를 더한 값을 다음 값으로 추가하는 방식으로 만든 수열을 의미한다.

이를테면 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 ,,, 의 순서로 이어지며 n=6인 경우 8이 출력된다.

def fib(n):
    if n<=2:
    	return 1
    else:
    	return fib(n-1) + fib(n-2)

이는 n에서 n-1, n-2인 수를 더해주는 식으로 

fib(5) = fib(4)+fib(3)

fib(4) = fib(3)+fib(2)

fib(3) = fib(2)+fib(1)

fib(2) = fib(1)로 진행된다.

 

첫번째와 두번째자리 수는 1로 고정되기에 n<=2는 1로 반환한다.

---

재귀함수를 활용한 하노이의 탑 옮기기

하노이의 탑이란 원반이 n개인 하노이의 탑을 옮기기 위한 원반 이동 순서를 출력하는 알고리즘이다.

하노이의 탑 규칙은 다음과 같다.

 크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮겨야 합니다.
• 원반은 한 번에 한 개씩만 옮길 수 있습니다.
• 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아, 다른 기둥의 맨 위로만 옮길 수 있습니다(기둥의 중간에서 원반을 빼내거나 빼낸 원반을 다른 기둥의 중간으로 끼워 넣을 수 없습니다).
• 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없습니다

즉, 1->3 기둥으로 원반을 옮기기 위해서 2번 기둥을 보조적으로 사용하는 것

def hanoi(n, from_pos, to_pos, aux_pos):
    if n==1: ##종료규칙 (원반이 1개일 경우 마지막 기둥으로 바로 옮김)
    	print(from_pos,'->',to_pos)
        return
    hanoi(n-1, from_pos, aux_pos, to_pos) ## 최종 원반을 제외하고 나머지 원반을 보조기둥으로 옮김
    print(from_pos,'->', to_pos)
    hanoi(n-1, aux_pos,to_pos, from_pos) ## 보조기둥에 있던 원반을 최종 원반으로 옮겨야 하기에 처음 기둥을 보조기둥으로 활용

print('n=1')
hanoi(1,1,3,2)
print('n=2')
hanoi(2,1,3,2)
print('n=4')
hanoi(4,1,3,2)