Published on

코딩테스트 재귀함수

Authors
  • avatar
    Name
    Hyo814
    Twitter

재귀 함수는 자신을 호출하는 함수로, 반복 작업을 간단히 표현할 수 있어 코딩 테스트에서 자주 사용됩니다.

1. 팩토리얼 계산 (Factorial)

문제: 숫자 n의 팩토리얼을 계산하라.

팩토리얼 정의:

n! = n * (n-1) * (n-2) * ... * 1

0! = 1

코드

function factorial(n) {
  if (n === 0) {
    return 1 // 기본 종료 조건
  }
  return n * factorial(n - 1) // 재귀 호출
}

console.log(factorial(5)) // 출력: 120

2. 피보나치 수열 (Fibonacci Sequence)

문제: 피보나치 수열의 n번째 숫자를 구하라.

피보나치 수열 정의:

fib(0) = 0, fib(1) = 1

fib(n) = fib(n-1) + fib(n-2) (n >= 2)

코드

function fibonacci(n) {
  if (n === 0) return 0 // 기본 종료 조건
  if (n === 1) return 1 // 기본 종료 조건
  return fibonacci(n - 1) + fibonacci(n - 2) // 재귀 호출
}

console.log(fibonacci(6)) // 출력: 8

3. 배열의 합 계산

문제: 주어진 숫자 배열의 합을 재귀로 계산하라.

코드

function sumArray(arr) {
  if (arr.length === 0) return 0 // 기본 종료 조건
  return arr[0] + sumArray(arr.slice(1)) // 첫 요소 + 나머지 배열 합
}

console.log(sumArray([1, 2, 3, 4, 5])) // 출력: 15

4. 이진 탐색 (Binary Search)

문제: 정렬된 배열에서 주어진 값을 찾아 해당 인덱스를 반환하라.

재귀를 이용하여 배열의 중간값과 비교하며 탐색.

코드

function binarySearch(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1 // 기본 종료 조건: 값이 없음

  const mid = Math.floor((start + end) / 2)
  if (arr[mid] === target) return mid // 찾은 경우
  if (arr[mid] > target) {
    return binarySearch(arr, target, start, mid - 1) // 왼쪽 탐색
  }
  return binarySearch(arr, target, mid + 1, end) // 오른쪽 탐색
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 5)) // 출력: 2

5. 문자열 뒤집기

문제: 문자열을 뒤집어서 반환하라.

코드

function reverseString(str) {
  if (str.length === 0) return '' // 기본 종료 조건
  return reverseString(str.slice(1)) + str[0] // 나머지 뒤집기 + 첫 문자
}

console.log(reverseString('hello')) // 출력: "olleh"

재귀 함수 이해를 위한 팁

  1. 기본 종료 조건: 재귀는 항상 기본 종료 조건이 필요합니다. 종료 조건이 없으면 무한 루프에 빠져 에러가 발생합니다.
  2. 작은 문제로 나누기: 문제를 더 작은 문제로 쪼개고, 이 작은 문제를 반복해서 해결합니다.
  3. 스택 활용: 재귀 호출은 호출 스택(Call Stack)에 쌓이기 때문에 메모리 사용량에 주의해야 합니다.