[알고리즘] 재귀 함수 (Recursion)

🌀 재귀 (Recursion)

재귀란, 실행 과정에서 자기 자신을 호출하는 함수다.

'자기 자신을 호출한다'는 말이 자기 자신으로 '반복해서 돌아간다'는 의미를 내포하는 것 같다면, 맞다. 모든 재귀 함수는 반복문(while문 또는 for문)으로 표현할 수 있다. 그렇다면 반복문과 무슨 차이가 있나?

완벽한 비유는 아니지만, 여기 러시안 인형이 있다. 러시안 인형은 첫 번째 인형을 열면 그속에 더 작은 인형이 있다. 그리고 이것을 반복하다보면, 너무 작아서 더 이상 작아질 수 없는 크기까지 인형이 있다는 것을 확인할 수 있다. 재귀도 그렇다.

재귀는 반복 호출을 통해 계속해서 문제를 가장 작은 단위까지 쪼개는 것으로, 문제 해결의 한 방식으로 이해할 수 있다.

💁‍♀️ 반복문과의 차이

for(int i = 0; i < arr.length; i++){...}

예시로 배열에 들어간 요소의 합을 반복문으로 구한다고 생각해보면, 이런 코드로 구할 수 있을 것이다.

그런데, 배열의 요소로 숫자만 들어있는 게 아니라 배열이 겹겹이 들어있다면 for문 안에 for문을 (필요한 횟수만큼) 넣어야 할 것이다. 계산이 전혀 불가능한 것은 아니나 이렇게 해결할 경우 오류가 나기 쉽고, 코드가 몹시 지저분해질 것이다.

return num + arrSum(num-1);

이럴 때 arrSum이라는 메서드를 만들고, 재귀로 arrSum을 계속 호출하면 반복문을 실행하는 것과 같은 효과를 누리면서 훨씬 간결한 코드를 쓸 수 있다.

🤔 재귀는 언제 사용할까?

(1) 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
(2) 반복문이 많이 중첩되거나 중첩 횟수를 예측하기 어려운 경우
(3) 변수 사용을 줄여 mutable state를 제거해 프로그램 오류가 발생할 가능성을 줄이고자 하는 경우

주의: 대부분의 경우 재귀를 활용하면 반복문의 경우보다 코드가 훨씬 간결하다. 그렇다고 해서 반복문보다 효율적인 것은 아니다. 고로 재귀를 쓸 수 있다고 해서 무조건 재귀를 쓰는 것은 바람직하지 않다.

종결문이 없거나(무한 재귀), 종결문이 절대 참이 될 수 없는 경우, 또는 매우 큰 수를 재귀 함수로 돌린다면 컴퓨터 메모리에 공간이 없을 때까지 계속해서 같은 메서드를 호출 스택에 푸시한다. 이로 인해 스택 오버플로라는 오류가 발생한다.

👉 재귀 작성법

int factorial (number) {
if (number == 1)  // 베이스 케이스
return 1;
return number * factorial(number -1); // 재귀함수
}

Base case

재귀함수가 종결할 부분이다. 예시 코드의 경우,

number = 3일 때,

number == 1이 TRUE가 될 때까지 재귀를 반복한다.

factorial(3) -> 3 * factorial(2)
factorial(2) -> 2 * factorial(1)
factorial(1) -> number == 1 TRUE -> return 1;

종결문에 도달하여, 메서드는 종료된다. 

1이라는 값을 가지고 다시 factorial(1)을 호출한 곳으로 돌아간다.

factorial(2) -> 2 * 1 = 2
factorial(3) -> 3 * 2 = 6

factorial(3)은 종료되면서 결과값 6을 반환한다.

Recursive case

위 설명에서 보았듯이, Recursive case는 종결문에 도달할 때까지 계속 자기 자신을 호출하는 구문이다. 러시안 인형의 가장 작은 부분에 도달할 때까지 크기를 줄여나가는 모습을 상상하면 이해가 쉽다.

✨ 재귀 활용 예제

피보나치 수 구하기

public int fibonacci(int num){
	if(num < 2)
    return num;
    return fibonacci(num-2) + fibonacci(num-1);

num = 4 인 경우,
fibonacci(4) -> fibonacci(2)+fibonacci(3) 
fibonacci(3) -> fibonacci(1)+fibonacci(2) 
fibonacci(2) -> fibonacci(0)+fibonacci(1) 

fibonacci(0) -> num < 2 TRUE -> return 0;
fibonacci(1) -> num < 2 TRUE -> return 1;

fibonacci(2) -> 0 + 1 = 1
fibonacci(3) -> 1 + 1 = 2
fibonacci(4) -> 1 + 2 = 3

fibonacci(4)는 종료되면서 결과값 3을 반환한다.

배열의 길이 구하기

public int arrayLength(int [] arr){
	if(arr.length == 0) return 0;
    int [] tail = Arrays.copyOfRange(arr, 1, arr.length)
    return 1 + arrayLength(tail);
    
배열이 {1, 2, 3, 4}일 때,
int[] tail = {2, 3, 4}; // 3 + 1 = 4
int[] tail = {3, 4}; // 1 + 2
int[] tail = {4}; // 0 + 1
int[] tail = {}; -> arr.length == 0 TRUE -> return 0;

종결문에 도달되고, 주석처리한 내용대로 리턴값을 가지고 돌아간다.

arrayLength(int [] arr)는 종료되면서 결과값 4를 반환한다.