1. 재귀란?
함수가 자기 자신을 호출하는 것
: A way of solving problems by calling function itself
앞으로 다루게 될 '퀵 정렬'과 재귀를 활용한 탐색 알고리즘을 위해
'재귀'에 대해 더 알아보자.
2. 기저조건이란?
무한 호출을 멈추게 하는 중단 조건을 의미한다.
따라서,
재귀함수를 정의하거나 다른 재귀함수를 읽을때
기저조건이 무엇인지를 가장 먼저 확인한다.
3. 재귀 함수 예시
[1] 10에서 0까지 카운트 다운하는 프로그램
def count_down(num):
print(num)
if num == 0:
return
else:
count_down(num-1)
count_down(10)여기서 기저조건은
if num == 0:
return일 때다.
num의 값이 0일때, 함수는 return을 시작한다.
그러면 0이 출력되는 건 알겠는데, 1, 2,3, 4, ..., 10 은 어떻게 출력되는걸까
컴퓨터 관점에서 보면
1) count_down(10)이 호출된다.
2) print(10) 코드를 작동한다. (10 출력)
3) count_down(9)를 호출한다.
.
.
.
count_down(0)이 호출한다.
print(0) 코드 작동한다. (0 출력)
return
이제 여기서 호출스택 개념이라는 것이 생겨난다.
편의상 count_dowon 함수를 f 라고 하겠다.
f(10) -> f(9) -> ... -> f(0) 이 진행될때,
컴퓨터의 호출 스택(LIFO)엔 아래와 같은 구조가 되어 있다.
f(0) : top
f(1)
.
.
.
f(9)
f(10) : bottom
물론 이번 예제에서는 호출스택이 작동되는 걸 느끼기 어렵다.
왜냐하면,
else:
count_down(num-1)
count_down(10)count_down(num-1) 다음줄에 추가로 진행되는 코드가 없기 때문이다.
예를 들어, f(10)이 호출됐다고 하자.
만약에
count_down(num-1) 다음에 코드가 남아있다고 하자.
컴파일러(인터프리터)는 f(9)를 먼저 실행시키고
그 아래에 남아있는 코드들의 경우 이후에 처리하게 된다.
'이후에' 처리하는 작업들의 순서를 컴퓨터가 기억해야 하므로
그걸 스택에 저장하게 되는 것이다.
[2] 다른 예제를 통해 좀더 알아보자.
이번엔 팩토리얼(계승)값을 리턴해주는 재귀함수다.
def factorial(num):
if num == 0:
return 1
else:
return num * factorial(num-1)
result = factorial(5)
print(result)'기저조건'을 가장 먼저 생각해보자.
3! = 3 x 2 x 1
4! = 4 x 3 x 2 x 1
5! = 5 x 4 x 3 x 2 x 1
즉,
num가 계속 1씩 차감되어 호출되니
num가 0까지 왔을때 리턴해줘야 한다.(=재귀함수 종료, 반환 시작)
재귀함수의 묘미는 큰 문제를 잘게잘게 쪼개서
가장 작은 단위에서 다루는 접근법이라는 것이다.
4. 스택 오버플로
컴퓨터 메모리에 더 이상 공간이 없음.
기저조건이 없는 재귀함수는 무한적으로 함수를 호출한다.
즉, 스택에 끊임없이 처리해야할 함수 목록이 쭉쭉 쌓여감을 의미한다.
그러다가 컴퓨터 메모리가 꽉차게 되면 '스택 오버플로'라는 오류가 발생하는 것이다.
그래서 기저조건을 설정하는 것은 매우 중요하다고 할 수 있다.
- One step at a time - 