[코드카타] 재귀함수 / 꼬리 재귀 / 꼬리 호출 최적화 TCO

https://school.programmers.co.kr/learn/courses/30/lessons/140108

프로그래머스

 

위의 연습문제를 재귀함수로 풀었다.

왜 재귀법을 생각했는지?

1. 문자열을 순회

2. 부분에 대해 같은 작업을 반복

3. 재귀 호출이 끝나는 조건 (base case) 이 명확

#include <string>

using namespace std;

int recursion(string s) {
    if (s.empty()) return 0;
    if (s.length() == 1) return 1;
    
    char x = s[0];
    int same = 0;
    int different = 0;

    for (int i = 0; i < s.length() - 1; i++) {
        if (s[i] == x) same++;
        else different++;
        
        if (same > 0 && same == different){
            return 1 + recursion(s.substr(i+1));
        }
    }
    return 1;
}

int solution(string s) {
    return recursion(s);
}

 

예) recursion("banana") 라면

1 + recursion("nana")

     1+ recursion("na")

           1 + recursion("")

                 0

= 3

 

예2) recursion("abracadabra") 라면

1 + recursion("racadabra")

      1 + recursion("cadabra")

            1 + recursion("dabra")

                  1 + recursion("bra")

                        1 + recursion("a")

                              1

= 6

출처 : https://wayhome25.github.io/cs/2017/04/15/cs-16-1-recursion/

출처 : https://zorba78.github.io/cnu-r-programming-lecture-note/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98recursive-function.html

 

재귀함수와 메모리

함수 호출 시 (지역, 매개)변수, 반환 주소값이 스택 메모리에 저장된다.

따라서 재귀 호출 시 재귀함수의 정보가 호출 스택에 '쌓이고' 이에 더해 함수가 실행된 후 다시 호출된 위치로 돌아올 때 '컨텍스트 스위칭' 의 비용이 있어 반복법보다 비효율적일 수 있다.

또한 너무 깊거나 base case가 잘못 설정된 재귀호출은 스택 오버플로우를 일으킬 수 있다.

 

참고: https://velog.io/@yonghyeun/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%9D%98-%EC%9E%A5%EC%A0%90%EA%B3%BC-%EB%8B%A8%EC%A0%90-%ED%95%B4%EA%B2%B0%EC%B1%85

재귀함수는 무엇이고 장점과 단점이 무엇일까 ?

 

실제로 위 연습문제도 코드를 제출 했을 때 각 케이스마다 생각보다 오랜 시간 & 많은 메모리를 차지했다.

꼬리 재귀 Tail Recursion

: 재귀함수가 반환하는 값이 재귀호출의 반환값인 경우

즉, 재귀 함수가 return 하기 직전에 다른 연산 없이 재귀 호출만 있는 경우이다. (i.e. Tail Call)

 

예) 팩토리얼을 구하는 함수를 꼬리 재귀로 구현 (feat. ChatGPT)

int factorial_helper(int n, int accumulator) {
    if (n == 0) return accumulator;
    return factorial_helper(n - 1, n * accumulator); // TCO would reuse the same stack frame.
}

int factorial(int n) {
    return factorial_helper(n, 1);
}

 

꼬리 호출 최적화 Tail Call Optimization (TCO)

컴파일러에 따라서 꼬리 재귀 호출을 새로운 스택 프레임으로 콜스택에 쌓는 것 대신 변수만 업데이트하여 해당 스택 프레임을 재사용하게 (jump) 한다.

이렇게 최적화하는 것을 TCO라고 하며, 앞서 말했듯 프로그래밍 언어, 컴파일러에 따라 지원 여부가 다르다.

 

C++의 경우 공식적으로 지원되는 것은 아니나, GCC나 Clang 같은 컴파일러는 최적화 설정에 따라 TCO를 수행한다.

만일 스택 오버플로우가 걱정될 정도로 깊은 재귀라면, 별도의 스택 자료구조를 재귀에 활용하여 iterative 한 접근을 해야 한다.

 

참고: https://www.youtube.com/watch?v=Hqs7KYwSd0A&ab_channel=%EC%A3%BC%EB%8B%88%EC%98%A8TV%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98%EC%97%B0%EA%B5%AC%EC%86%8C

 

위에 내가 작성한 코드의 경우 꼬리 재귀를 적용하면 아래처럼 바꿔볼 수 있겠다.

#include <string>

using namespace std;

int recursion(string s, int count) {
    if (s.empty()) return count;
    if (s.length() == 1) return count + 1;
    
    char x = s[0];
    int same = 0;
    int different = 0;

    for (int i = 0; i < s.length() - 1; i++) {
        if (s[i] == x) same++;
        else different++;
        
        if (same > 0 && same == different){
            return recursion(s.substr(i+1), count + 1);
        }
    }
    return count + 1;
}

int solution(string s) {
    return recursion(s, 0);
}

 

그러나... 해당 문제에서는 시간, 메모리 효율적인 반복적 접근

#include <string>
#include <iostream>

using namespace std;

int solution(string s) {
    int answer = 0;
    int same = 1; // first character is a match
    int different = 0;
    char x = s[0];
    
    if (s.length() <= 2) return 1;
    
    for (int i = 1; i < s.length(); i++) {
        if (s[i] == x) {
            same++;
        } else {
            different++;
        }
        
        if (same == different) {
            same = 0;
            different = 0;
            answer++;
            x = s[i + 1]; // null character if i+1 == s.length()
        }
    }
    
    if (same > 0) answer++; // if the last 'substring' had at least one character, count it
    
    return answer;
}

 

재귀적인 접근보다 월등히 빠르고 (18ms vs. 0.04ms) 메모리도 적게 차지한다.

 

한줄평

재귀 함수는 선택적으로 써야겠다... 코드는 쉽지만 느리고 무거운... 양날의 검...