[알고리즘/java] 재귀함수

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

재귀함수란 ? 

- 간단히 함수 내에서 자기 자신을 호출하는 함수라고 할 수 있다.

알고리즘 문제 유형 중 DFS(깊이우선탐색), BFS(넓이우선탐색)에 쓰이기 때문에 꼭 알아두어야 한다. 

 

 

아래 예시 문제로 재귀함수의 원리를 간단하게 설명할 수 있다.

 

문제 : 

자연수 N을 입력하면 1~N까지 재귀를 이용해 출력하시오.

 

 

 

<자연수 3을 입력한다고 가정한 코드>

 

* if문 (종료 조건)을 작성해주지 않으면 무한반복이 됨

 

main에서 DFS(3)을 호출하게 되면, 스택프레임이 스택에 저장된다.

-> 스택프레임은 매개변수, 지역변수, 복귀주소의 형태이지만 밑에서는 이해하기 편하게 간단히 표시했다.

 

DFS(3)을 실행하면서 line7에서 DFS(2)가 호출되어 스택프레임이 스택에 저장된다.

DFS(2)을 실행하면서 line7에서 DFS(1)가 호출되어 스택프레임이 스택에 저장된다.

 

DFS(1), line7

DFS(2), line7

DFS(3), line7

 

그리고  DFS(1)을 실행하면서 line7에서 DFS(0)이 호출되는 순간, n==0이기 때문에 return을 만나 함수가 종료되면서 

가장 상단 부분 즉,  현재 작동중인 스택프레임이 pop된다.

 

DFS(0), line7

DFS(1), line7

DFS(2), line7

DFS(3), line7

↓

DFS(1), line7

DFS(2), line7

DFS(3), line7

 

 

그 다음 상단인 DFS(1) 스택프레임이, line7 다음인 line8로 넘어가 1을 출력하고 함수 종료 후, pop

 

그 다음 상단인 DFS(2) 스택프레임이, line7 다음인 line8로 넘어가 2을 출력하고 함수 종료 후, pop

 

그 다음 상단인 DFS(3) 스택프레임이, line7 다음인 line8로 넘어가 3을 출력하고 함수 종료 후, pop

 

 

DFS(3)호출이 끝났기 때문에(스택에 남은 것이 없음) 다시 main함수로 돌아오게 된다.

 

 

 

---

한 가지 유의점은

DFS메소드 내에서 n을 출력하는 8번 라인을 재귀함수 이전에 넣느냐 / 후에 넣느냐에 따라 출력하는 값이

3 2 1이 되거나 1 2 3이 된다.