[Algorithm] 재귀와 반복문 중 무엇을 사용해야 할까?

개요

알고리즘 문제를 풀다 보면 반복적인 규칙이 있는 문제가 있습니다.

이런 문제들은 재귀 함수를 이용해서 풀 수도 있고, 반복문을 이용해서 풀 수 있습니다.

대표적인 문제가 팩토리얼 문제입니다.

입력으로 순서가 주어지면 팩토리얼 값을 구하는 방법은 다음과 같이 재귀함수를 이용해서 풀 수 있고 반복문을 이용해서 풀 수 있습니다.

 

팩토리얼 문제를 푸는 2가지 방법 - 재귀, 반복문

public class Solution {
  public static int factorialUsingRecursion(int num) {	// 재귀
    if (num == 0)
      return 1;
    else
      return num * factorialUsingRecursion(num - 1);
  }

  public static int factorialUisngIteration(int num) {	// 반복
    int result = 1, i;

    for (i = 2; i<=num; i++)
      result *= i;

    return result;
  }

  public static void main(String[] args) {
    int num = 5;
    System.out.println("입력이 " + num + "이고 재귀를 사용했을 때 결과값: "
            + factorialUsingRecursion(5));
    System.out.println("입력이 " + num + "이고 반복문을 사용했을 때 결과값: "
            + factorialUisngIteration(5));
  }
}

 

결과값을 두 값 모두 같고, 결국 방법만 다르다는 것을 알 수 있습니다. 

그러면 언제 재귀함수를 사용하고 언제 반복문을 사용할까요?

 

재귀함수를 사용해야 하는 경우

1. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우

문제에서 반복되는 규칙이 재귀적인 표현이 쉬운 문제들이 있습니다. 대표적인 예가 피보나치수열입니다. 피보나치 수열은 다음과 같이 표현할 수 있습니다.

fibo(n) = fibo(n-2) + fibo(n-1) (n>=2, n은 정수)

n번 째 값을 구하기 위해서 재귀함수를 이용하여 바로 앞 두 요소를 더하면 됩니다. 이러한 알고리즘은 재귀적으로 그리고 직관적으로 매우 자연스럽습니다. 그래서 문제를 쉽게 풀 수 있는 장점이 있습니다.

 

2.가독성을 높이고 싶은 경우

재귀함수는 성능이 좋지 않습니다. 반복적으로 함수를 호출할 때마다 메모리 스택 영역에 호출함수가 쌓이게 됩니다.(계속 쌓여 스택 공간을 넘어서면 스택오버플로우가 발생합니다) 이러한 자원의 소비가 반복문을 사용해서 소비하는 자원보다 많습니다. 하지만 현재는 H/W가 좋지 못해 소프트웨어를 통한 성능을 극한으로 올리는 시대가 아닙니다. 또한 과거보다 메모리의 용량도 많이 커졌습니다. 그렇기 때문에 성능의 이점보다 협업하는 상황을 고려한 가독성 향상이 더 큰 이점을 가져온다고 생각하면 재귀함수를 사용하는 것도 좋습니다.

 

3.변수의 사용을 줄여 프로그램 안정성을 높이고 싶은 경우

재귀를 사용하면 반복문을 사용할 때보다 사용하는 변수의 갯수가 적습니다. 위의 코드예시를 보더라도 재귀 함수를 사용할 때 사용한 변수는 num 하나인 반면, for을 사용하면 num, result, i 총 3개의 변수를 사용합니다. 그렇기 때문에 반복문으로 짠 코드는 상대적으로 변경 가능성이 높고 이는 예기치 못한 오류로 이어질 수 있습니다. 따라서 프로그램의 안정성을 높이고 싶다면 재귀함수를 사용하는 것도 나쁘지 않습니다.

 

 

이번에는 반대로 반복문을 사용해야하는 경우를 알아보겠습니다.

 

반복문을 사용해야 하는 경우

1.성능을 최대한 끌어올리고 싶은 경우

이유는 한 가지이지만 강력한 이유입니다. 만약 최적의 성능을 요구하는 상황이라면 재귀보다 반복문을 사용해야 합니다. 예를들어 풀려고하는 코딩테스트 문제의 제한시간이 0.5초입니다. 보통 주어지는 시간이 1초라고 한다면 성능을 최대한으로 끌어올려 문제를 풀어야 통과할 수 있습니다. 이럴 때에는 두 가지 중 반복문을 선택해야합니다.

 

정리

특징	재귀(Recursion)	반복문(Iteration)
정의(Definition)	자기 자신을 호출하는 메소드	일련의 명령어들을 반복해주는 명령문
사용(Application)	function	loop
종료(Termination)	if(탈출조건)~else	종료 조건이 거짓일 때
사용	1.자연스러운 표현 2.가독성 3.안정성	성능이 중요할 때
가독성	좋음	나쁨
시간복잡도(Time Complexity)	매우 높음	상대적으로 낮음

 

---

Reference

https://www.geeksforgeeks.org/difference-between-recursion-and-iteration/

Difference between Recursion and Iteration - GeeksforGeeks

https://kldp.org/node/134556

https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0