[자료구조/알고리즘] 재귀

재귀 함수

• 재귀 함수는 자기 자신을 호출하는 함수다.

why?

• 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽습니다.
• 함수형 프로그래밍 기법 중 하나입니다.

---

활용

• 재귀를 사용하여 문제를 풀기 적절한 상황은 다음과 같습니다.

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우 (ex : 선물 속의 선물, 마트료시카)
   

• 이론적으로 재귀함수를 사용해 문제를 해결하기 위해서는 문제를 가장 작은 단위까지 더는 작아지지 않을 때 까지 문제를 쪼개고 해결합니다. (말이 쉽지)

• 기본적으로 base case 와 recursive case를 염두하여 함수를 만들어야 합니다.

1. base case : 탈출문, 계속해서 자신 함수를 호출할 때 base case의 조건이 성립되면 호출을 멈추고 base case의 return 값을 재귀 함수의 인자로 전달해 계산합니다.
2. recursive case : 자신을 호출하는 문장, 어떤 형식으로 재귀를 원하는 지 매개변수를 조작한다.

---

재귀 함수와 메모리 사용량 간의 관계

• 재귀를 사용하다 보면, 이따금 아래와 같은 상황을 보곤 합니다

• 탈출문을 잘못 작성하면 브레이크 기능을 하지 못하면 스텍 오버플로우를 일으킬 수 있습니다.
  그럼에도 알고리즘이 for문을 사용할 때 보다 가독성이 좋고, 변수의 사용량을 줄일 수 있기 때문에 오류 발생 확률을 낮출 수 있다고 합니다.

• 이를 대처하기 위해 꼬리재귀 최적화를 사용할 수 있습니다.

• 꼬리재귀 최적화는 컴파일러가 컴파일 하는 시점에 스택 프레임을 재사용 할 수 있도록 일반적인 for, while 문과 비슷한 형태로 코드를 변환하는 기법입니다.

일반적인 재귀 함수 예시 :

function factorial(n){
	if(n == 1) {
      return 1;
    }
    return n * factorial(n - 1);
}

---

꼬리 재귀 최적화 함수 예시 :

function factorial(n){
  if(n === 1){
    return n;
  }
  let result = fac(n-1);
  return n*result;

1. 두 코드의 스텍창을 확인하면 일반적인 재귀함수는 스텍이 계속 쌓이게되고 꼬리재귀는 한번만 호출 됩니다.
2. 일반적인 재귀함수는 리턴 값이 함수이기 때문에 계속 해서 함수를 호출하고, 꼬리재귀는 함수를 호출하고 그 함수를 변수에 할당하고 사용합니다.
3. 그래서 더 이상 함수에서 추가 연산이 일어나지 않습니다. 스텍이 계속 쌓이는 재귀의 단점을 보완한 것이 꼬리함수 입니다.