[자료구조] 재귀 함수를 호출할 때

def factorial(n):
	return factorial(n-1)*n
    
for i in range(1, 7):
	print(factorial(i))

Base Case : 재귀함수가 더 이상 호출되지 않도록 하는 특정 조건

 

프로그램에서 함수를 호출하면 내부적으로 '스택 프레임' 이라는 내부 공간이 생긴다.

스택 프레임은 함수를 호출할 때 생성되고, 함수 실행이 종료되었을 때 소멸된다.

Base Case가 없으므로 한번 호출된 factorial 함수는 실행이 종료되지 않아 소멸이 되지 않고, 자기 자신을 연쇄적으로 호출하면 서 스택프레임이 계속 쌓이게 된다.

스택 프레임은 메모리에 생성되는데, 최대 한계치에 다다르면 RecursionError를 일으킨다.

 

factorial() 함수에 Base Case를 추가해보자. 

def factorial(n):
    # Base Case
    if n==0:
        return 1
    return factorial(n-1)*n

for i in range(1, 7):
	print(factorial(i))

잘 실행이 된 것을 볼 수 있다.

 

 

 

결론 : 재귀 함수에 Base Case를 두지 않으면 계속 호출이 일어나고 스택 프레임이 저장되는 메모리는 한정적이기 때문에 무조건 오류가 발생한다.