재귀 함수 호출 (1)

함수를 재귀적으로 호출하기

 

반복과 재귀는 복잡한 작업을 하나씩 작게 나누어 처리하고 그 결과를 조합한다는 면에서는 동일하다.

 

◾ 반복

필요한 처리를 계속 반복하면서 유지하는 것을 강조. 파일 스트림을 끝까지 읽을 때처럼 한계치까지 특정 처리를 실행할 때 주로 사용된다.

◾ 재귀

작업을 해결할 수 있을 때까지 작은 조각으로 나누는 것을 강조. 팩토리얼 등을 계산할 때 주로 사용된다.

 

반복으로 함수 호출

int factorial(int n)
{
    int result = 1;
    for (int i = 1; i <= n; ++i) result *= i;
    
    return result;
}

for (int i = 1; i < 10; ++i)
    std::cout << i << "! = " << factorial(i) << '\n';

 

 

재귀로 함수 호출

int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

for (int i = 1; i < 10; ++i)
    std::cout << i << "! = " << factorial(i) << '\n';

 

재귀 호출이 많아지면 콜스택이 쌓여서 결국 스택 영역이 부족해지는 문제가 발생하게 되는데, 이 문제는 뒤에서 나올 꼬리 재귀에서 다룬다.

물론 위의 코드같은 경우는 콜스택이 쌓이기 전에 오버플로우로 인해 프로그램이 미정의 동작을 하게 될 수 있다.

 

 

 

 

불변 함수 반복 호출

 

재귀 함수는 상태를 변경할 필요가 없기 때문에 함수형 프로그래밍과 매우 잘 어울린다.

 

int fibonacci(int n)
{
    if (n == 0) return 0;
    
    int previous = 0;
    int current = 1;
    
    for (int i = 1; i < n; ++i) { // 값의 변경이 일어났기 때문에 순수 함수가 아니다
        int next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

 

반복문을 사용하는 함수의 경우 값이 변하기 때문에 불변 객체가 아니다.

 

int fibonacci(int n)
{
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 

재귀를 사용하면 코드가 간결해질 뿐만 아니라 자연스럽게 불변 객체가 된다.

마찬가지로 아직까지는 콜스택이 쌓이는 문제가 있다.