재귀 (Recursion)

PS를 하면서 느낀점이 지금까지 코딩 해온 경험으로 어떻게든 억지로 문제를 풀고 있다는 느낌이 들어서 기초 알고리즘을배우면서 다시 기초를 다져보자는 생각이 들었다.

트리나 힙, 최소경로 이런 것도 대충 손으로 쓰라고 하면 쓰겠는데 코드로 짜라하면 뭔가 애매한 느낌이고,

좌표압축같은 문제도 제대로 못푸는걸 보니까 확실히 기초가 딸린다는 생각이 들더라..

---

재귀란 '자기 자신을 참조하는 행위'이다.

 

재귀 함수의 예로 피보나치 수를 구하는 방법도 있고, ( cache를 만들어주지 않으면 시간복잡도 멸망 )

※ 피보나치 수를 구하는 문제 : https://www.acmicpc.net/problem/2747

public long getFibonacci(int index) {
    if(index <= 1) return index;
    return getFibonacci(index-1) + getFibonacci(index-2);
}

 

더 흔한 방법으로는 팩토리얼도 있다.

※ 팩토리얼을 구하는 문제 : https://www.acmicpc.net/problem/10872

public long getFactorial(int num) {
    return num == 1 
        ? 1 
        : getFactorial(num-1) * num;
}

 

재귀는 굉장히 간단한 개념이지만, 아주 쓸 곳이 많다.

 

반복적 패턴이 있는 도형을 그리는 문제, (https://www.acmicpc.net/problem/2447)

DFS(깊이 우선 탐색), BFS(너비 우선 탐색)과 같이 트리를 탐색할 때,

단순히 반복을 대체할 때 등 다양한 사용처가 있다.

 

잘 쓰면 굉장히 유용한 개념인데, 사용할 때 주의할 점이 있다.

return 문에 재귀함수를 넣어야한다면, 연산 없이 재귀함수만 넣어야된다는 건데

예를 들어 위의 팩토리얼 코드를 바람직하게 바꿔보면

public long getFactorial(long current, int num){
    if(num == 1) return current;
    return getFactorial(current*num, num-1);
}

대충 이런 느낌이다.

 

이런 최적화 방식을 Tail Call이라고 한다.

Context Switching이라던가.. 뭐 그런 Memory Overhead와 관련된 이유가 있는데, 좀 간단하게 풀어서 getFactorial(5)와 getFactorial(1, 5)를 호출한다고 생각하고 예시를 들어보겠다.

 

먼저 getFactorial(5)의 경우 이런 연산이 진행될 것이다.

getFactorial(5)
 -> 5 * getFactorial(4)
 -> 5 * 4 * getFactorial(3)
 -> 5 * 4 * 3 * getFactorial(2)
 -> 5 * 4 * 3 * 2 * getFactorial(1)
 -> 5 * 4 * 3 * 2 * 1
 -> 5 * 4 * 3 * 2
 -> 5 * 4 * 6
 -> 5 * 24
 -> 120

위의 getFactorial이 진행되는 동안 5*, 4*, 3*와 같은 연산자들은 재귀적으로 호출된 getFactorial의 값이 반환되어야 함수가 종료될 수 있고, 함수가 종료되지 않았다면 함수 내 변수의 Scope라던가, Stack에 할당된 메모리 등이 반환되지 않기 때문에, 재귀의 횟수가 많아질수록 오버헤드가 커진다.

 

그러면 getFactorial(1, 5)를 보자.

getFactorial(1, 5)
-> getFactorial(5, 4)
-> getFactorial(20, 3)
-> getFactorial(60, 2)
-> getFactorial(120, 1)
-> 120

새롭게 재귀함수를 호출하면서 이미 값에 대한 연산이 진행됬기 때문에, 이전 함수는 모두 종료된 상태이다.

마지막 리턴도 결국 먼저 호출된 재귀함수들의 return문들을 타고 돌아가야하니까 종료되면 안되는게 아닌가?라는 생각이 들 수 있지만, 결국 마지막 반환값이 최초 호출장소로 리턴되면 되기 때문에 최초 호출인 getFactorial(1,5)의 위치만 알면 사이에 실행된 함수들은 모두 종료해도 아무 지장이 없게 하는 것이 Tail Call Optimization의 역할이다.

 

물론 프로그래밍 언어가 TCO를 지원해야 의미가 있는 작성방식이고, Java는 stackTrace가 어렵다는 점 등으로 인해서 지원하지 않는다고한다.