윤성우의 열혈 자료구조를 읽고 복습한 내용입니다.

재귀의 활용

피보나치 수열: Fibonacci Sequence

피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열로 다음과 같이 전개된다.

쉽게 말하면, '앞의 것 두 개를 더해서 현재의 수를 만들어가는 수열'이다. 처음 두 개의 수 0과 1이 주어진 상태에서 수를 만들어 가게 된다. 따라서 피보나치 수열의 n번째 위치의 값을 반환하는 함수는 수학적으로 다음과 같이 표현된다.

const Fibo = (n) => {
  if(n === 1) return 0;
  else if(n === 2) return 1;
  else return Fibo(n-2) + Fibo(n-1);
}

for(let i=1;i<15;i++){
  console.log(Fibo(i));
}

/*
expected output:
0
1
1
2
3
5
8
13
21
34
55
89
144
233
*/

재귀함수가 대략적으로 이해는 되나, 함수의 호출순서가 파악되지 않아 찜찜하게 느낄 수 있다. 어떠한 순서대로 함수의 호출이 진행되는지 정리해 보자. Fibo 함수가 호출되면서 인자로 7이 전달되면, 이어서 Fibo 함수 내에 존재하는 다음 문장이 실행된다.

return Fibo(n-1) + Fibo(n-2); // return Fibo(6) + Fibo(5)

즉 두 개의 Fibo 함수가 다시 호출되는데, + 연산자의 왼편에 있는 Fibo 함수 호출이 완료되어야 비로소 + 연산자의 오른편에 있는 Fibo 함수 호출이 진행된다. 그렇기 때문에 아래 그림에 쓰여진 숫자의 순서대로 재귀적 함수 호출이 진행된다.

재귀함수의 호출 순서는 큰 의미가 없으니 참고하고, 재귀함수 자체를 이해하도록 노력하자.

이진 탐색 알고리즘의 재귀적 구현

앞서 구현했던 이진 탐색 알고리즘을 재귀함수 기반으로 구현해보자. 이 알고리즘을 수식적으로 표현하기에는 부적적하지만 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 구현 가능하다.

이진 탐색 알고리즘의 반복 패턴을 정리해보자.

1. 탐색 범위의 중앙에 위치한 값이 타겟과 일치하는지 확인한다.
2. 일치하지 않는다면 탐색 범위를 반으로 줄여서 다시 탐색을 시작한다.

탐색 실패가 결정되는 시점은 다음과 같다.

"탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우"

이것이 재귀함수의 탈출조건이 된다. 재귀함수의 탈출은 탐색 대상을 찾았거나 탐색 대상이 배열에 존재하지 않는 경우에 이뤄진다.

const BSearchRecur = (arr, target, first, last) => {

  if(first>last) return -1;

  let mid = Math.floor((first+last)/2);

  if(target === arr[mid])
    return mid;
  else if(target > arr[mid])
    return BSearchRecur(arr, target, mid + 1, last);
  else
    return BSearchRecur(arr, target, first, mid -1);
}

const arr = [1, 3, 5, 7, 9];
let idx;

idx = BSearchRecur(arr, 9, 0, arr.length - 1);

if(idx === -1) console.log("탐색 싧패");
else console.log("타겟 저장 인덱스:", idx);
// expected output: 타겟 저장 인덱스: 4

idx = BSearchRecur(arr, 8, 0, arr.length - 1);

if(idx === -1) console.log("탐색 싧패");
else console.log("타겟 저장 인덱스:", idx);
// expected output: 탐색 실패

재귀함수는 매우 많은 수의 함수 호출을 동반하기 때문에 성능상의 불리함이 분명 존재한다. 그럼에도 이진 탐색 알고리즘을 재귀함수 기반으로 구현하는 이뉴는 재귀함수에 익숙해지는데 그 목적이 있다.