재귀 함수 vs 반복 loop(김종민)

[rlajm1203]

문제가 무엇인가?

과연 재귀함수가 좋을까 반복 loop가 좋을까?

왜 이런 문제를 선정하였는가?

함수형 프로그래밍을 지향하기 위해서는, 함수나 메소드 내부에서는 참조 투명성을 준수하고, 예외 지양, 재귀를 지향하라고 했다.
재귀롤 사용하는 게 무조건으로 좋은 방법일까?

자신이 생각한 답변은 무엇인가?

반복문

• 반복문은, 명령을 반복적으로 실행시키기 위한 명령문이다.
• 반복문이 기계어로 변환되면, 많아야 7-10개의 기계어로 변환되어서 CPU가 이 7-10개의 명령어를 반복적으로 수행한다.

-> 프로그램의 명령어 및 모든 기계어는 컴퓨터의 메모리에 존재하므로, 반복문을 사용할 경우에 메모리 셀 7~10개만 사용하여 루프를 실행하므로 공간 측면에서 효율적이다.

재귀함수

• 함수의 바디에서 자신의 함수를 다시 호출하여 작업을 수행한다.
• 함수 호출 시 함수의 매개변수, 지역변수, 리턴 값, 함수 종료 후 돌아갈 메모리 주소 값 등이 스택 메모리에 저장
• 스택 오버 플로우 발생 위험
• 반복문보다 느리다.
• 메모리 사용량 많다.

왜 재귀 함수를 사용하는가?

속도도 느리고, 메모리 사용량도 많은데 왜 재귀함수를 사용하는가?

1. 변수 사용량 감소
2. 알고리즘 표현 용이 (알고리즘을 코드로 표현했을 때 이해하기 쉽다.)

public int fibonacci(int n){
  return n>=0 && n<=1 ? n : fibonacci(n-1) + fibonacci(n-2);
}

언제 재귀를 사용하는가?

1. 데이터 구조가 재귀적일 경우
2. 분할 정복 알고리즘

꼬리 재귀 함수

• 일반 재귀의 단점을 보완한 방식으로, **"재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법"**이다.
• 이 방식을 사용하면 이전 함수의 상태를 유지하지 않고 추가 연산이 없으므로 스택 오버 플로우가 일어나지 않는다.
• 함수의 꼬리 부분에서 실행되며 return 되기 전에 값이 정해지며, 호출당한 함수의 결과 값이 호출하는 함수의 결과 값으로 반환된다.
  • 스택 프레임을 재사용

꼬리 재귀의 핵심은 호출 당한 함수의 결과 = 호출한 함수의 결과 이다.
(또한 꼬리 재귀를 이용하기 위해서는, 컴파일러가 꼬리 재귀를 지원해야 한다.)

return factorial(n - 1, n * total);

return n * factorial(n - 1);

꼬리 재귀 이외의 해결책

1. 메모이제이션 : 이전 계산 결과 저장

• 우리가 일반적으로 아록 있는 피보나치 재귀함수는, 중복 계산이 매우 많다.

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoization {
    private static Map<Integer, Long> memo = new HashMap<>();

    public static long fibonacci(int n) {
        // 기본 케이스
        if (n <= 1) {
            return n;
        }

        // 메모에 이미 계산된 값이 있는지 확인
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // 새로운 값 계산
        long result = fibonacci(n - 1) + fibonacci(n - 2);

        // 계산된 값을 메모에 저장
        memo.put(n, result);

        return result;
    }

    public static void main(String[] args) {
        int n = 50;
        long startTime = System.nanoTime();
        long result = fibonacci(n);
        long endTime = System.nanoTime();

        System.out.println("Fibonacci(" + n + ") = " + result);
        System.out.println("Calculation time: " + (endTime - startTime) / 1000000 + " ms");
    }
}

50번째 피보나치 항을 구하는 경우

• 메모이제이션 재귀

• 일반 재귀

결론

반복문을 사용할지, 재귀를 사용할지는 아주 어려운 고민거리라고 할 수 있다.

시간 복잡도와 공간 복잡도를 비교해놓고 봤을 때, 프로젝트나 문제 상황에서 우선시 되는 것을 선택하면 될 것 같다.

• 시간 복잡도 및 공간 복잡도 중요 : 반복문
• 코드 가독성 및 간결성이 중요할 경우 : 재귀 (되도록이면 일반 재귀 대신, 꼬리 재귀나 메모이제이션 기법 사용)