재귀함수
자기 자신을 다시 호출하는 함수
재귀함수가 호출되면 컴퓨터 시스템의 스택 프레임에 함수가 반복적으로 쌓여서 마지막으로 호출된 함수가 처리된 이후에 그 함수를 불렀던 함수까지 처리되는 방식인데, 이 형태가 실제로는 스택과 같은 형태로 동작한다고 이해할 수 있다.
종료 조건을 명시해서 함수가 무한히 호출되지 않게 해야한다.
최대공약수 계산 예제
두 개의 자연수에 대해 최대공약수를 구하는 대표적인 알고리즘으로 유클리드 호제법이 있다.
<유클리드 호제법 >
- 두 자연수 A,B(A>B)가 있을 때 A를 B로 나눈 나머지를 R이라고 하자.
- A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
유클리드 호제법 역시 재귀 함수로 작성할 수 있다.
dfs(Depth-First-Search)
깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조, 혹은 (간결하게 작성하기 위해서) 재귀함수를 이용해서 구현하기도 한다.
<동작과정>
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면
그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번을 수행할 수 없을 때까지 반복한다.
