반복문과 재귀 방식의 차이점은 무엇이고 꼬리 재귀란 무엇인가?

[ahah525]

문제

예제를 통해 반복문과 재귀 방식의 차이점에 대해 알아보고 꼬리 재귀란 무엇인지 학습해보자.

관련 목차

• [18장] 함수형 관점으로 생각하기

참고자료

[ahah525]

💡반목문 vs 재귀 함수

1. 반복문과 재귀함수의 차이점

	반복문	재귀함수
정의	명령을 반복적으로 실행	함수를 다시 호출하여 반복 작업 수행
스택 메모리	스택 메모리 사용X	함수 호출 시 함수의 매개변수, 지역변수, 리턴값, 함수 종료 후 돌아갈 위치를 스택 메모리에 저장
무한반복	조건식이 계속 참이면 무한 루프 발생 → CPU 사이클을 반복적으로 사용	종료 조건에 수렴하지 않으면 무한 재귀 발생 → 스택 오버플로우 발생
속도	빠른 실행	느린 실행
가독성	코드 길이가 길고 변수가 많아 가독성이 낮음	코드 길이 짧고 변수가 적어 가독성이 높음

📍스택 오버플로우(Stack Overflow)

함수가 호출될 때마다 매개변수, 지역변수, 리턴값, 함수 종료 후 돌아갈 위치 등의 정보가 스택 메모리에 저장된다.

재귀함수는 함수의 실행이 끝나기 전에 함수를 연속적으로 호출하므로 스택 메모리를 초과하면 스택 오버플로우가 발생한다.

반목문은 지역변수가 호출될 때 한 번만 스택 메모리에 할당되기 때문에 무한 루프가 발생하더라도 스택 오버플로우가 발생하지 않는다.

2. 재귀함수의 장단점

2.1. 장점

1. 코드가 짧아지고 가독성이 높아진다.
2. 변수 사용을 줄여준다.
   • 반복문에서 사용하는 반복 변수같은 mutable state(변경 가능한 상태)를 제거하여 프로그램 오류 발생 가능성을 줄인다.

2.2. 단점

1. 반복적 함수 호출로 인해 반복문에 비해 메모리 사용량이 높고 속도가 느리다.
2. 함수 호출 후 복귀를 위한 컨텍스트 스위칭 비용이 발생한다.

📍컨텍스트 스위칭(Context Switching)

여러 개의 프로세스가 실행되고 있을 때 기존에 실행되던 프로세스르 중단하고 다른 프로세스를 실행하는 것

💡꼬리 재귀(Tail Recursion)

재귀함수의 메모리 성능에 대한 단점을 보완하기 위한 방법이 바로 꼬리 재귀다.

재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법

1. 꼬리 재귀 최적화를 위한 2가지 조건

2가지 조건을 만족한다면 컴파일러는 꼬리 재귀 최적화를 지원해 자체적으로 재귀함수를 반복문으로 변경해서 실행한다.

1. 재귀 함수를 꼬리 재귀 방식으로 구현할 것
   • return 문에 추가적인 연산이 없도록 구현해야 함
2. 컴파일러가 꼬리 재귀 최적화를 지원할 것
   • 컴파일러가 꼬리 재귀 최적화를 지원하지 않는다면 꼬리 재귀 방식으로 구현해도 최적화X

2. 자바의 꼬리 재귀 최적화

자바 컴파일러는 꼬리 재귀 최적화를 지원하지 않는다.

하지만, 자바 8에서 반복을 스트림으로 대체해 변화를 피할 수 있다.

💡factorial 예제를 통한 반복문, 재귀, 꼬리 재귀 방식의 비교

1. 반복문

명령을 반복적으로 실행하는 것

// 반복문
public int factorialIterative(int n){
    int res = 1;
    for(int i = 1 ; i <= n ; i++){
        res *= i;
    }
    return res;
}

@Test
@DisplayName("[반복문]")
void t1() {
    factorialIterative(5);
}

• 매개변수, 지역변수가 스택 메모리에 할당된다.

2. 재귀

한 함수가 자신을 다시 호출하여 반복 작업을 수행하는 것

// 일반 재귀
public int factorialRecursive(int n){
    if(n == 1) return 1;
    return n * factorialRecursive(n - 1);
}

@Test
@DisplayName("[재귀 ]")
void t2() {
    factorialRecursive(5);
}

• 호출당한 함수의 결과값에 추가 연산한 값을 반환한다.
  • 호출한 함수 : factorialRecursive(n)
  • 호출당한 함수 : factorialRecursive(n - 1)
  • 호출한 함수의 결과값 : n * factorialRecursive(n - 1)
• 재귀 호출 이후 추가 연산을 하기 때문에, 함수 종료 후 돌아갈 위치를 스택 메모리에 저장해야 한다.

3. 꼬리 재귀

// 꼬리 재귀
// acc : 연산 결과값을 전달하기 위한 매개변수
public int factorialTailRecursive(int n, int acc){
    if(n == 1) return acc;
    return factorialTailRecursive(n - 1, n * acc);
}

@Test
@DisplayName("[꼬리 재귀]")
void t3() {
    factorialTailRecursive(5, 1);
}

• 호출 당한 함수의 결과값이 호출하는 함수의 결과값으로 반환된다.
  • 호출한 함수 : factorialRecursive(n, acc)
  • 호출당한 함수 : factorialRecursive(n - 1, n * acc)
  • 호출한 함수의 결과값 : factorialRecursive(n - 1, n * acc)
  • 즉, 가장 마지막으로 계산된 acc 값이 그대로 반환된다.
• 재귀 호출 이후 추가 연산을 하지 않기 때문에, 함수 종료 후 돌아갈 위치를 스택 메모리에 저장할 필요가 없다.

Reference

• 반복문 vs 재귀
  • 반복문(iteration) vs 재귀(recursion)*
  • 재귀함수의 장점과 단점 그리고 해결책
  • [Algorithm] 반복문(iteration) vs 재귀(recursion)
• 꼬리 재귀
  • 꼬리 재귀 (Tail Recursion)*
  • 재귀함수와 꼬리 재귀
  • [Play with Java] Java 8로 꼬리재귀 함수 만들기 (Tail Recursion)