(자료구조,알고리즘) 재귀

재귀 함수(Recursion Function)란?

재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.

그렇기에 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.

우리가 흔히 알고 있는 반복문은 for, while 등이 있는데
이러한 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.

재귀함수의 대표적인 예제

factorial

1    // 반복문으로 구현한 팩토리얼 메서드
2     public int Factorial(int number) {
3       int result = 1;
4       for(int count = number; count > 0; count--) {
5         result = result * count;
6   }
7       return result;
8   }
9
10   // 재귀 호출로 구현한 팩토리얼 메서드
11   public int Factorial(int number) {
12     if(number <= 1) {
13        return 1;
14     }
15      return number * Factorial(number - 1);
16   }

재귀함수의 장점

1. 불필요하게 여러개의 반복문을 사용하지 않는다.
2. 코드가 간결해지고, 수정이 용이하다.
3. 변수를 여러개 사용할 필요가 없다.

재귀함수의 단점

1. 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵다.
2. 이러한 과정은 반복문에 비해서 메모리를 더 많이 사용하게 되어 많은 메모리를 사용하게 된다.
3. 메서드를 호출하고 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 된다.
4. 반복하여 매서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 된다.

재귀함수를 사용하기 위한 조건

1. 문제의 크기를 점점 작은 단위로 쪼갤수 있어야 한다.
2. 재귀 호출이 종료되는 시점이 존재해야 한다.