코딩 테스트 - 재귀함수의 함정(+영상 설명)

0. 들어가며

재귀함수의 개념이 익숙한 분들은 코딩테스트에서 잘 사용하시는 분들이 많을 겁니다.

1. 코드가 직관적이어보이는 장점도 있고
2. 내가 생각한 수식/알고리즘을 곧잘 표현하기 아주 좋은 방식이기 때문입니다.

하지만 코테 연습 사이트(programmers에서나 leetcode같은 곳)에서는 재귀함수를 썼을 때 모든 test case를 만족하지 못하는 경우가 있습니다.

 

왜 재귀함수는 코테에 적합하지 않을까요?

1. 문제는 stack memory

재귀함수의 문제를 아시려면 먼저 프로그램이 실행될 때의 메모리 공간이

heap 메모리
stack 메모리

둘로 나뉘어져 있다는 것을 아셔야 합니다.

heap tree의 heap이나, queue/stack의 stack과는 전혀 관련없는 내용입니다.

 

heap 메모리 영역은 런타임 단계에서 사용되는 메모리 영역으로 동적으로 할당되는 메모리 영역입니다.

반면 stack 메모리 영역은 compile단계에서 사용되고, 함수 호출에서 사용되는 메모리 영역입니다.

 

함수 call에서 함수 안의 변수가 저장되는 memory 영역은 stack memory 영역입니다.

이 stack memory 영역의 변수가 차지하는 메모리 공간은 함수 호출이 끝날때 다시 메모리에 반납됩니다.

stack memory 설명

그런데, stack memory 영역과, heap memory의 특징이 있는데요.

stack memory 영역은 접근이 빠르지만, 크기가 작습니다.
heap memory 영역은 접근은 stack보다 느리지만, 크기가 큽니다.

그렇기 때문에 test case에서 일부러 메모리를 크게 사용하도록 한다면!

stack memory 영역이 가득찼다고 에러를 보이게 되어 test case 실패가 일어나게 됩니다 ㅠㅠ

 

 

재귀함수와 stack 메모리에 대한 상관관계는 아래 영상에서 확인하실 수 있습니다 :)

 

영상:

https://www.youtube.com/watch?v=7V_kVMb8YBI