함수가 자기 자신을 호출하는 것
: A way of solving problems by calling function itself
앞으로 다루게 될 '퀵 정렬'과 재귀를 활용한 탐색 알고리즘을 위해
'재귀'에 대해 더 알아보자.
무한 호출을 멈추게 하는 중단 조건을 의미한다.
따라서,
재귀함수를 정의하거나 다른 재귀함수를 읽을때
기저조건이 무엇인지를 가장 먼저 확인한다.
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까지 왔을때 리턴해줘야 한다.(=재귀함수 종료, 반환 시작)
재귀함수의 묘미는 큰 문제를 잘게잘게 쪼개서
가장 작은 단위에서 다루는 접근법이라는 것이다.
컴퓨터 메모리에 더 이상 공간이 없음.
기저조건이 없는 재귀함수는 무한적으로 함수를 호출한다.
즉, 스택에 끊임없이 처리해야할 함수 목록이 쭉쭉 쌓여감을 의미한다.
그러다가 컴퓨터 메모리가 꽉차게 되면 '스택 오버플로'라는 오류가 발생하는 것이다.
- One step at a time -