100만 재귀를 들어가고, 들어갈 때마다 20바이트씩 사용한다고 하더라도 약 20MB밖에 되지 않습니다.

한 depth당 얼만큼의 메모리가 필요한지 어떻게 계산하는건가요??

전역변수를 제외하고 dfs에 들어가있는 지역변수만 해당되는 건가요??

전역 변수는 재귀 호출과는 무관하니 별도로 계산해야 합니다.

재귀호출되는 함수에 선언되는 지역 변수와 함수 호출 스택만이 영향을 받는데, 정확한 크기는 사용하는 프로세서에 따라서 조금씩 달라질 수 있으나 많아도 수십 바이트 이상 넘어가지는 않을 것입니다.

예전에 풀었던 문제중에 잘 기억이 안나는데.. depth가 1만이상 갔을때 터지는걸 경험을 했었는데.. 그땐 재귀 함수의 메모리가 많이 차지해서 그런건가요??

그건 단순히 메모리의 총량이 많아서 생긴 문제가 아니라, 재귀 호출 스택과 지역 변수가 스택 영역을 사용하기 때문에 그런 것입니다. 스택 영역은 전체 메모리 한도와는 별개로 프로그래마다 배정이 되어 있는데, 이는 윈도우즈에서는 기본적으로 1MB, 리눅스에서는 8MB로 설정되어 있습니다. 하지만 이는 빌드 시에 설정을 따로 해줄 수 있고, BOJ에서는 제가 알기로는 64MB 정도까지 스택을 허용하기 때문에 문제가 되지 않습니다.

아 그렇군요.. 그런것도 잘 알고 있어야 메모리 계산을 하고 특정 풀이를 생각하겠네요 감사드립니다.