꼬리 재귀 (Tail Recursion)

c++로 풀었던 백준 문제를 파이썬으로 변환하다가 메모리 초과가 났다.

이유가 뭔지 찾아봤는데 이유는 다음과 같았다.

 

1. c++도 그렇지만 파이썬도 재귀함수를 호출하면 함수가 끝나지 않은채 함수가 또 호출되기 때문에 스택 메모리에 메모리가 계속 쌓이게 된다.

 

2. 그런데 나는 지금까지 c++에서 재귀 함수의 사용으로 메모리 초과를 경험한 적이 없다. (적어도 내 기억에는) 

 

3. 이유는 바로 꼬리 재귀 (Tail Recursion) 때문 이었다.

 

꼬리 재귀 

꼬리 재귀란 재귀 함수의 호출이 끝난 후 아무 연산을 하지 않고 바로 반환하는 재귀이다. 

예를들어 다음과 같은 깊이 우선 탐색을 구현한 재귀 함수는 

void dfs(int r, int c, int cnt, int dir, vector<vector<int>> &v)
{
    if(cnt == 0) return;
    if(cnt == num) { ansR = r; ansC = c; }

    v[r][c] = cnt;
    int nr = r + dr[dir];
    int nc = c + dc[dir];

    // 범위 벗어나거나 이미 숫자있으면 방향 바꿈
    if(nr < 0 || nr >= N || nc < 0 || nc >= N || v[nr][nc] != 0)
    {
        dir = (dir + 1) % 4;
        nr = r + dr[dir];
        nc = c + dc[dir];
    }

    dfs(nr, nc, cnt-1, dir, v);
}

(그냥 썼던 코드를 갖고 온 것이니 위의 코드는 신경쓰지말자) 

함수의 마지막 부분에 재귀 함수를 호출한다. 

즉 함수의 호출 후 아무런 연산도 하지 않는다. 

이런 재귀를 꼬리 재귀라고 하는데 이런 꼬리 재귀의 경우 재귀 함수의 결과의 값이 변할 여지가 없기 때문에 (함수 호출 후 아무런 연산도 하지 않기 때문에) 컴파일러가 스택을 재활용함으로써 스택 메모리를 아껴준다.

 

이런 이유 때문에 지금까지 c++로 재귀 함수를 구현했을때 (주로 깊이 우선 탐색) 메모리 초과가 나지 않았던 것이다.

파이썬으로 바꿔 쓴 코드는 메모리 초과가 난 이유는 파이썬은 컴파일러에서 이런 꼬리 재귀를 인지하고 스택 재활용해주는 기능이 없기 때문이다.

 

 

 

 

https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion

Does Python optimize tail recursion?

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

Tail Recursion Elimination

위 링크에 따르면 파이썬 개발자는 TRE (Tail Recursion Elimination) 자체가 파이썬스럽지 않아서 지원하지도 지원할 예정도 없다고 한다.