재귀 함수 호출 (2)

꼬리 재귀 이해하기

 

일반적인 재귀 함수와 다르게 꼬리 재귀는 함수 끝에서 자기 자신을 호출하는 것 외에 더 해야 할 일이 없다.

 

int factorialTail(int n, int i)
{
    if (n == 0) return i;
    return factorialTail(n - 1, n * i);
}

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

 

기존 재귀함수에서 사용되던 n * factorial(n - 1)은 함수의 호출이 끝나도 연산이 남아있기 때문에 꼬리재귀가 아니다.

꼬리재귀로 구현하는 경우 콜스택이 소비되지 않는다. (단, 컴파일러의 최적화 옵션이 켜져있어야 한다)

 

 

 

 

함수형, 절차형, 백트래킹 재귀

 

표준 용어는 아니지만 함수형 재귀, 절차형 재귀, 백트래킹 재귀로 구분한다.

 

함수형 재귀

재귀적으로 문제를 풀면서 각 결과 값을 합치고 그 값을 반환한다.

앞서 다뤘던 팩토리얼, 피보나치가 이에 해당한다.

 

 

절차형 재귀

함수 내부에서 필요한 작업을 바로 처리하여 반환값이 없다.

 

void doPermute(const std::string& chosen, const std::string& remaining)
{
    if (remaining == "") std::cout << chosen << '\n';
    else {
        for (uint32_t u = 0; u < remaining.length(); ++u) {
            doPermute(chosen + remaining[u],
                remaining.substr(0, u) + remaining.substr(u + 1));
        }
    }
}

void permute(const std::string& s)
{
    doPermute("", s);
}

 

순열을 출력하는 함수의 경우 별도의 값 반환 없이 함수 내부에서 작업을 처리할 수 있다.

 

 

백트래킹 재귀

마치 ctrl+z(실행취소) 한것처럼 스택을 되감아서 돌아갈 수 있다.

미로찾기나 순열 등에 사용할 수 있다. DFS와 개념이 유사하다.