재귀 함수 정리

하이 ... 

요즘은 정말 틈틈이 시간을 내서 알고리즘을 열심히 공부하고 있는 중이다.

 

예전에 취업 준비할 때는 알고리즘에 대해 자신감도 있었고, 문제도 곧잘 풀었었는데 뭔가 공부를 다시하려니 마음먹은대로 쉽게 되진 않는다.

 

사설이 조금 길었다.

 

오늘은 알고리즘 문제에서 다양하게 많이 사용되는 재귀함수에 대한 내용을 정리해 두려고 한다.

 

1. 스택 프레임

 

먼저 재귀함수에 대해 알기 위해서는 스택 프레임이라는 것을 잘알아야 한다.

 

스택 프레임이란 스택 영역에 차례로 저장되는 함수의 호출 정보를 의미한다.

보통의 언어에서 메모리의 스택 영역은 함수의 호출이랑 그와 관련된 지역 변수와 파라미터를 저장한다.

이 스택영역은 함수의 호출이 완료되면 소멸된다.

 

우리가 흔히 들어본 스택 오버플로우가 바로 이 영역이 넘쳐버리는 현상을 의미한다.

 

2. 재귀함수

 

이렇게 스택 프레임에 대해 열심히 설명한 이유가 있다.

 

아래의 코드는 1~5 까지 숫자를 차례로 출력하는 것을 for문을 이용하지 않고 재귀를 이용하여 출력한것이다.

위 코드는 내부에서 재귀함수를 호출하고 있는 형태를 보인다. 아래 그림을 보면 아래의 순서로 스택이 처리됨을 알 수 있다.

간단하게 말씀드리자면 스택에는 함수가 호출 될때 호출되는 라인 정보까지 같이 쌓이는데 상단의 스택이 처리가 되고 나서 본인의 작업이 처리될때는 그다음라인부터 수행하게된다. 그렇기 때문에 위처럼 1 2 3 4 5 이렇게 출력이 될수 있는 것이다.

 

 재귀함수의 경우 내부에서 계속 함수를 호출하기 때문에 성능이 좋진 않지만... 다양한 알고리즘 문제를 풀때 자주 사용되니 원리를 잘 이해하길 바란다. 

 

끝.