재귀의 이해

• 재귀함수(recursion function): 자기 자신을 호출하는 함수
• 재귀의 필요성
  • 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  • 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
  • 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

⚠️ 모든 재귀 함수는 반복문(while문 또는 for문)으로 표현 가능함

재귀의 활용

재귀함수 작성 가이드

1. 재귀 함수의 입력값과 출력값 정의하기

2. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.

   • 일반적으로, 입력값을 기준으로 판단한다.
   • 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분한다.
     • 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같도록 문제 구분하기
   • 문제에서 주어진 입력값에 따라, 경우의 수를 나누기
     • 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눔

3. 재귀의 기초부터 구성하기
   base case: 재귀 함수에서 재귀의 탈출 조건 (재귀 호출이 멈추는 조건)을 구성

4. 재귀할 조건 구성하기
   recursive case

재귀함수의 형식

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

예시

팩토리얼 함수

function factorial(num) {
  if(num===0) return 1
  return num * factorial(num-1)
}

• 화살표 함수와 삼항 연산자로 더 간단하게 작성하기

const factorial = num => num === 0 ? 1 : num * factorial(num - 1)

피보나치 수열

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