알고리즘 - 재귀(Recursive), 꼬리 재귀(Tail recursive)

재귀란?

---

재귀는 자기 자신을 호출하는 함수이다. 알고리즘이 임의의 단계만큼 깊이 들어가야 한다면 재귀가 좋은 방법일 수 있다.

 

재귀 함수 분석 방법

---

1. *베이스 케이스를 찾는다
2. 베이스 케이스에서 함수가 어떻게 동작하는지 살핀다.
3. 베이스 케이스 바로 이전의 조건을 찾는다.
4. 베이스 케이스 바로 이전의 조건에서 함수가 어떻게 동작하는지 확인한다.
5. 이전의 조건으로 거슬러 올라가면서 코드가 어떻게 동작하는지 확인한다.

이렇게 재귀 함수는 베이스 케이스부터 거꾸로 올라가면서 추론하는 방법이 유용하다.

 

*BaseCase

베이스 케이스는 함수가 반복되지 않는 경우이다. 즉, 함수가 더 이상 자기 자신을 호출하지 않아서 종료되는 조건이다. 모든 재귀 함수는 무한으로 호출하지 않도록 베이스 케이스가 반드시 하나 이상 있어야 한다.

 

*Recursive Case

리커시브 케이스는 자기 자신을 호출하는 부분으로, 문제를더 작은 부분으로 분해한다.

 

Stack

---

const factorial = (number) => { // 재귀함수
	if(number === 1) return 1;
    
    return number * factorial(number - 1);
}

factorial(3)을 실행했을 때 callstack

Call stack

컴퓨터는 스택을 사용해서 어떤 함수를 호출하고 있는지 기록하는 데 이것을 콜스택이라고 한다. 콜스택을 통해 값 위로 전달하기를 진행하면서 각 재귀 함수는 계산된 값을 부모 함수에 반환하고 최초로 호출된 함수가 최종 값을 계산한다.

 

Stack overflow

무한 재귀에서는 컴퓨터가 같은 함수를 콜스택에 푸시한다. 단기 메모리에 더 이상 데이터를 저장할 공간이 없을 때까지 콜스택은 점점 늘어난다. 사용할 수 있는 메모리보다 많이 호출하게 되면 스택 오버플로우가 발생한다.

 

재귀 함수가 유용한 경우

---

1. 알고리즘이 얼마나 깊이 들어가야 하는지 모르는 상황에서 문제를 여러 단계로 파고들어야 하는 경우
2. 하위 문제의 계산 결과에 기반해 계산할 수 있는 경우

 

하위 문제

하위 문제는 기본 문제와 동일하지만 입력을 더 작게한 문제이다.

계산 함수를 작성할 때에는 두 가지 방식이 있다.

• 상향식 계산 : 상향식 계산에서는 재귀와 루프 둘의 계산 방식이 같다.
• 하향식 계산 : 하향식 사고방식은 문제를 해결하는 새로운 사고 전략을 제공하기 때문에 재귀는 하향식 방식을 구현하는데에 탁월하다.

 

하향식 사고 절차

1. 작성하고 있는 함수가 이미 구현되어 있다고 가정한다.

2. 문제의 하위 문제를 찾는다.

3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작한다.

 

하향식 사고 절차 예시 문제

* 배열합 구하기

주어진 배열 [1, 2, 3, 4, 5] 내 모든 수를 합하는 sum이라는 함수를 작성한다. 이 함수에 위 사고 절차를 적용해보자.

 

1. sum 함수가 이미 구현되어 있다고 가정하고 잘 동작한다고 가정한다.

2. 하위 문제를 찾는다. 여기서 하위 문제는 첫 번째 원소를 제외한 [2, 3, 4, 5] 이다.

3. 하위 문제에 함수를 호출하면 어떻게 되는지 본다. sum 함수는 이미 잘 작동한다고 가정하므로, sum([2, 3, 4, 5])를 호출하면 14가 나온다. 그 결과에 1만 더하면 된다.

 

코드로 작성하면 다음과 같다.

return arry[0] + sum(array.slice(1));

const sum = (array) => {
	if(array.length === 1) return array[0];
    
	return array[0] + sum(array.slice(1));
}

 

꼬리 재귀 함수

---

꼬리 재귀 함수란 재귀 함수를 호출할 때 실행된 코드를 남겨두지 않고 반환하는 함수이다. 꼬리 재귀 최적화가 가능한 언어는 함수를 호출하기 전에 함수가 어디로 돌아와야 하는지 미리 알고 있다. 새로운 함수를 호출할 때 돌아올 곳을 지정할 수 있기 때문에, 스택을 사용하지 않고도 스택을 제거하고 메모리를 아낄 수 있다. 꼬리 재귀는 무조건 반복문으로 바꿀 수 있다.

 

const factorial = (number, acc = 1) => {
	if(number === 1 ) return acc;
    
    return factorial(number - 1, acc * number);
}

 

위 코드에서 계속해서 바뀌는 값인 number와 acc를 변수로 선언한다. 그리고 재귀 함수 호출로 값을 변경하는 대신 변수의 값을 변경한다. 그다음 반복문을 만들고 number대신에 current의 값이 1이 되면 반복문을 종료하도록 수정한다. 이는 아래 코드와 같다.

 

const factorial = (number) => {
	let current = number
    	acc = 1;
    
   while(true){
   	if(current === 1) return acc;
    
    acc = acc * current;
    current = current - 1;
   }
};

이렇게 더 이상 재귀 함수 호출을 없앰으로써 콜 스택으로 메모리를 낭비하지 않고 더 효율적인 코드로 최적화 할 수 있다.

 

재귀 알고리즘의 예

• 피보나치 수열, 팩토리얼 구하기
• 병합 정렬, 퀵 정렬
• 이진 검색
• 트리 탐색, 중위, 전위, 후위 등 여러 트리 문제들
• 그래프 탐색, 깊이 우선 탐색과 너비 우선 탐색
• 동적 계획법의 예
• 분할 정복 알고리즘
• 하노이의 탑
• 백트래킹 알고리즘