[알고리즘] 재귀함수

안녕하세요 재귀함수와 스택프레임에 대해 알아보겠습니다.

 

재귀함수란(Recursive function)?

• 함수가 자기 자신을 호출하여 작업을 수행
• 반복하는 작업을 수행할 수 있음
• 함수 내에서 자신을 호출한 후 호출한 함수가 끝날 때 까지 함수 호출 이후의 코드는 수행되지 않음
• 반복문과 마찬가지로 종료 지점을 명확하게 생각하고 구현해야 무한루프를 방지할 수 있음

 

우리가 보통 반복되는 작업을 사용할 때 for문을 많이 쓰듯이 똑같이 재귀함수를 통해 구현할 수 있습니다.

 

코드를 보겠습니다

 

1부터 3까지의 수를 차례로 출력하라는 문제를 재귀함수로 풀어보겠습니다.

여기서 코드를 보시면 메인함수에서 DFS함수를 호출하고, 프린트하고 다시 DFS 자신을 호출합니다

이게 재귀함수입니다. 이렇게 하면 3 2 1 이런식으로 찍히겠죠?

하지만 종료 지점을 명시해 주지 않았기 떄문에 3 2 1 0 -1 .... 무한대로 찍히거나 스택오버플로우가 일어납니다.

 

그래서 이렇게 if문으로 n이 0이 됬을때 함수를 종료하도록 처리를 했습니다.

이러면 출력값이 3 2 1 이렇게 나오겠죠

하지만 저희는 1 2 3 이렇게 나오기를 원합니다.

 

이렇게 프린트문과 DFS 호출하는 구문을 바꿔주면 1 2 3으로 출력이 됩니다.

 

코드를 보면 재귀함수의 특성 상 함수 호출 후의 프린트문은 실행되지 않고

DFS 함수만 반복 된 뒤 if문을 타고 return 될텐데

프린트문은 언제 실행 될까요

여기서 스택프레임 개념이 나옵니다

 

스택프레임?

함수가 호출되면 스택 영역에 지역변수, 매개변수, 호출이 끝난후 돌아갈 반환 주소값이 저장됩니다.

이렇게  스택에 차례대로 저장되는 함수의 호출 정보를 stack frame이라고 합니다.

 

출처 TCP School

예시 이미지입니다. 밑에서 부터 함수가 호출 될때마다 쌓이게 됩니다.

우리 코드로 봤을때는 반환 값이 3 - 2 - 1 순서대로 쌓인거죠

 

출처 TCP School

이렇게 쌓인 값들은 함수가 종료 될 때 pop 되면서 데이터를 인출합니다.

스택은 후입선출(LIFO, Last In First Out) 구조이기에 맨 위에 있는 값부터 반환되죠.

 

그러면 우리가 원하는 1 2 3 순서로 나오게 됩니다.

 

 

좀 전에 종료 지점을 명시해 주지 않아 스택오버플로우가 발생했던 경우는

재귀호출에 의해 스택 프레임이 계속해서 쌓였던 것입니다.

스택의 모든 공간을 다 차지하고 난 후 더 이상의 여유 공간이 없을 때 또 다시 스택 프레임을 저장하게 되면

출처 TCP School

이렇게 스택오버플로우가 발생하게 되는 것입니다.