반복과 재귀 : DFS 문제를 재귀로 구현하면 편리한 이유

For문과 재귀함수

for문과 재귀함수는 '반복'을 실행할 때 사용한다는 점에서 공통점을 가지고 있다.

 

처음 반복문을 배울 때 대부분 for문으로 배우기 때문에, 나중에 재귀함수에 익숙해지기란 쉽지 않다.

그럼에도 재귀를 알아야하는 이유는 '함수호출과 스택 메모리' 때문일 것이다.

 

재귀는 '스택 메모리'를 활용한다는 특징 때문에 깊이우선탐색(DFS)과 같은 특정 알고리즘 문제를 해결할 때 유용하게 쓰이는데, 그 이유에 대해서 알아보자.

 

 

 고급 프로그래밍 언어에서 함수를 호출하게 되면, 운영체제는 스택 메모리라는 곳에 그 함수만 사용할 메모리 공간을 할당해준다. 그 함수 안에서 또 함수를 호출하면, 스택 메모리에 재귀적으로 호출된 함수들의 메모리 공간이 계속 쌓이게 된다.

 즉, 가장 먼저 불린 함수는 자기 안에서 호출된 함수들이 다 끝나서 나올 때까지 스택 메모리의 최하단에서 자신의 메모리를 유지한 채 기다리게 된다. 이렇게 되면 가장 안쪽의 함수를 먼저 수행하고 그 결과를 가지고 제일 마지막에 먼저 시작한 함수의 연산을 수행하는 흐름을 만들 수 있을 것이다.

 

for문의 경우 반복이 실행될 때마다 이전에 수행한 코드의 변수 정보들을 개발자가 따로 자료구조에 저장하지 않는 이상 더 이상 사용할 수 없게 되는 반면, 재귀를 사용하면 함수가 호출되면 운영체제가 스택메모리에 원래 함수의 정보를 유지한다는 특징을 활용해서 개발자의 구현 측면에서 편리함을 얻을 수 있게 되는 것이다.

 

정리하자면,

for문으로 DFS와 같은 코드 흐름을 만들기 위해서는 개발자가 stack이라는 자료구조를 만들어서 필요한 정보들을 구조체 형식으로 저장하는 등 복잡한 절차를 거쳐야 하지만,

재귀로 구현하면 이 복잡한 절차를 운영체제가 알아서 해준다는 것이 개발자 입장에서 아주 편리하다고 할 수 있다.

 

 

이미지 출처: tcpschool.com/c/c_pointerArray_arrayPointer