재귀(Recursive)를 알아보자
들어가기 전에
알고리즘 공부를 하다보면 만나게 되는 재귀!
어려우면 한없이 어려워지고 숙달된다면 금방 사용할 수 있다고 하는 재귀 이것에 대해 알아보자.
재귀 넌 누구니?
첫번째 거울 속의 나, 두번째 거울 속의 나, 세번째 거울 속의 나... 어디까지 가야하나...
이렇게 지속적으로 스스로를 호출하는 것이 재귀라고 할 수 있다.
재귀 언제 끝나?
위 질문에서 생각해야 되는 핵심적인 답변은 다음과 같다.
- 자기 자신을 부르는 부분이 존재한다.
- 빠져나오는 종결 컨디션이 존재한다.
그럼 재귀 왜 사용해?
- 몇몇 문제에 대해 반복문 보다 더 직관적인 해결이 가능하다.
- 예를들어, 펙토리얼, 피보나치, 이진검색, DFS, 타워 오브 하노이 등이 있다.
- 비슷한 세부문제들이 반복될 때 사용된다.
재귀의 단점
- 재귀함수는 반복문보다 메모리를 더 사용한다.
- 순차적으로 A 가 마무리되고 B 가 실행되는게 아니라 A 가 실행되는 도중에 B 가 실행되고 C 가 실행된다.
☞ 코드가 복잡해지고 사람의 머리로 따라가려하다가 길을 잃게된다.
그동안 코드를 작성할 때 작업 방식은,
☞ 순차적으로 위에서 아래로 실행이되는 코딩
☞ 하나의 동작이 마무리 되면 종료가 되고, 하나의 동작 세트가 있을 때 상위의 루틴이 마무리 되면 다음 서브루틴이 마무리되는 동작구조를 만들었다.
☞ 그런데 지금 사용하려는 재귀는 수행흐름이 시작 → 시작 → 시작 → 시작 → 시작 → 종료 → 종료 → 종료 → 종료 → 종료가 되는 흐름으로 일번 주자가 마지막에 종료가 되는 흐름이다. (정답과는 거리가 멀어지는 것 같은 기분이 든다...)
어디서 많이 본듯한 흐름 FILO(First In Last Out) 스택 구조로 동작한다.
실습
'백문이 불여일타'라고 하지 않았나 바로 코딩해보자.
# 재귀를 사용하지 않은 펙토리얼
def loop_fact(loop):
fact = 1
for i in range(loop, 0, -1):
if i == 0:
return
print("i:", i , ' fact:' , fact)
fact = i * fact
print(fact)
loop_fact(N)# 재귀를 사용하는 펙토리얼
def fact(n):
# 1. 종결 컨디션: '0'을 곱하면 안돼! '0'이되면 나가!
if n==0:
return 1
# 2. 셀프 호출: 처음에 '5' 가 주어지면 '5-1=4' 을 처음에 만들어야돼!
return n*fact(n-1)
print(fact(5))
결과 화면
위 코드를 보듯이 반복문을 사용하는 것보다 재귀를 사용했을 때 코드가 간결해졌다.
하지만, 재귀는 꿈속에 꿈속에 꿈을 차근차근 꿈을 깨어나면서 결과를 만들어내기 때문에 셀프 호출에 시작 시점과 종료 시점을 명확히 기준을 세우고 논리를 만들어야겠다.
솔직히 재귀를 다른 유형의 문제를 풀 때 잘 응용할 수 있을지는 모르겠지만 경험치를 조금씩 높이면서 해보려고 한다.
결국, 꾸준히 반복하는 것만이 답이다.. 알 때까지 반복 아니면 암기라도!