재귀

재귀(Recursion)란?

---

• 재귀란 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘 기법이다.
• 일반적으로 반복문을 사용하여 구현할 수 있는 문제를 재귀를 사용하여 구현할 수 있다.
• 재귀는 함수 내에서 자기 자신을 호출하므로, 작은 문제를 해결하고 다시 자기 자신을 호출하여 큰 문제를 해결한다. 이를 통해 복잡한 문제를 간단한 문제로 분해하여 해결할 수 있다.

 

재귀 함수의 구조

---

• 재귀 함수는 종료 조건과 작은 문제로 분해하는 작업이 필수적이다.
• 종료 조건은 재귀 호출을 멈추는 조건이며, 재귀 호출이 멈추지 않으면 무한히 재귀 호출이 반복될 수 있다.
• 작은 문제로 분해하는 작업은 재귀 함수를 호출하기 위한 입력 값의 범위를 축소시키는 작업이다.
• 작은 문제의 해답을 이용하여 큰 문제의 해답을 계산하는 작업도 필요하다.

function recursiveFunction(/* 매개변수 */) {
  if (/* 종료 조건 */) {
    // 종료 조건에 해당하는 경우 처리
  } else {
    // 문제를 작은 문제로 분해하는 작업
    // 작은 문제를 해결하기 위한 재귀 호출
    // 작은 문제의 해답을 이용하여 큰 문제의 해답 계산
  }
}

 

head와 tail

---

• head는 리스트(List)의 첫 번째 요소를 의미한다. 예를 들어, [1, 2, 3]이라는 리스트가 있을 때, head는 1이다.
• 재귀 함수에서 head를 사용할 때는 리스트의 첫 번째 요소를 처리하고 나머지 요소들을 다시 함수에 전달하여 재귀 호출을 수행다.
• tail은 리스트(List)의 첫 번째 요소를 제외한 나머지 요소들을 의미한다. 예를 들어, [1, 2, 3]이라는 리스트가 있을 때, tail은 [2, 3]이다.
• 재귀 함수에서 tail을 사용할 때는 리스트의 첫 번째 요소를 처리한 후, tail에 대해 같은 함수를 다시 호출하여 재귀 호출을 수행한다. 이러한 방식으로 리스트의 모든 요소를 처리할 수 있다.

 

 

예시: 피보나치 수열

---

function fibonacci(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

위의 함수는 피보나치 수열의 n번째 값을 반환한다. 함수 내부에서 n이 1 또는 2일 경우에는 1을 반환하고, 그 외의 경우에는 n-1번째와 n-2번째 수의 합을 반환한다. 이렇게 하면 재귀적으로 함수가 호출되면서 피보나치 수열을 구할 수 있다.