지금까지 여러 개의 작업을 반복문 하나로 유용하게 사용하여 해결하였다.

그러나 반복문의 단점은 배열에서 다차원을 다룰때 불편한 점이 명확하게 나온다.

예를 들어보자면

let arr = [a, b, c, [d, e], f, g]

해당 배열에서 d, e 배열 요소는 2차원 배열로 묶여있는 상태이다.

해당 요소는 [3][0]이므로 접근하기 위해서는 반복문 for-loop을 중첩으로 사용해야한다.

for(let i...) {
  for(let j...) {
   sum = sum + arr[i][j]
  }
}

그럼 만약 3차원에서 계속 여러 다차원으로 배열이 형성되면

중첩 반복문이 계속 필요하므로 하드 코딩이 쓰여진다.

이러한 목표 작업을 간단한 메커니즘 동작 하나로 단순화하기 위해서 존재하는 것이 바로 재귀 함수이다.

위와 같은 특정 자료 구조를 다룰때 자주 쓰이는 재귀 함수에 대해 알아보자.

---

재귀 베이스와 재귀 단계

function sum(x, n) {
  if (n === 1) {
    return x;
  } else {
    return x * sum(x, n - 1);
  }
}

sum(2, 4); // 16

위의 코드를 분석하면 함수 내에서 함수 자기 자신을 호출하는 재귀 단계 sum(x, n - 1) 를 볼수가 있다.

해당 코드를 통해 x를 n번 곱해주는 제곱 기능을 수행을 하게 된다.

그렇다면 조건문 if(n ===1)은 무슨 기능인지 궁금할텐데 이는 재귀의 베이스(base)라고 부르며

일종의 자전거 페달을 멈추게하는 브레이크 기능과 비슷하다.

재귀 함수가 연속적으로 호출을 반복하며 콜스택이 쌓이는 과정에

if(n ===1)이 성립된다면 멈추게 되는 것이다.

제곱 기능인 재귀 함수의 메커니즘을 순차적으로 나열해보자

1. sum(2, 4) = 2 * sum(2, 3)
2. sum(2, 3) = 2 * sum(2, 2)
3. sum(2, 2) = 2 * sum(2, 1)
4. sum(2, 1) = 2 (베이스에 접근되는 관계로 return x 만 호출)

숫자로 다시 표현 하자면

1. sum(2, 4) = 2 * 8
2. sum(2, 3) = 2 * 4
3. sum(2, 2) = 2 * 2
4. sum(2, 1) = 2

위 순서처럼 1번 값이 최종적으로 도출되는 것이다.

---

재귀 함수 응용 1 < ! 팩토리얼 >

function fac(n) {
  if (n <= 1) {
    return 1;
  } else { 
	return n * fac(n - 1); 
  }
}

fac(3); // 6

팩토리얼 공식 5! = 5 x 4 x 3 x 2 x 1 = 120

fac 함수 내 재귀 단계(recursive step) fac(n - 1)를 통해

절차적으로 콜스택이 4번 쌓이고 다시 소거될 것이다.

트리 구조를 통해 어떤 메커니즘이 형성되었는지 직접 수기로 작성해 보았다.

결국 재귀 함수를 통해 콜스택 진행 과정이 부메랑처럼 되돌아와 최종적으로 6이 출력된 것을 알 수가 있다.

---

재귀 함수 응용 2 < 피보나치 수열 >

function fib(n) {

    if (n <= 2) {
       return 1;
    } else {
       return fib(n - 1) + fib(n - 2)
    }
}

fib(5) // 5

재귀 단계(recursive step) fib(n - 1) + fib(n - 2)를 통해

콜스택이 4번 쌓인 것을 확인할 수 있다.

위의 트리 구조를 통해 콜스택이 다시 순회되며 9번의 진행 과정이 일어난 것을 알 수가 있다.

여기서 만약 fib(50) 을 호출한다면 콜스택이 몇 번 진행 될까? 아마 엄청난 횟수가 측정된다.

출력 전 복잡한 과정이 콘솔 엔진을 통해 가동되어,

콘솔창을 소환한 해당 웹 화면이 공백 상태로 다운된 것을 볼 수도 있을 것이다.

그런점을 유추한다면 해당 피보나치 수열을 재귀 함수로 사용하는 것은 매우 비효율적이다.

function fibo(n) {
    
    let result = [1, 1]

    // 피보나치 수열 [1, 1, 2, 3, 5, 8...]

    for (let i = 2; i <= n; i++) {
        result.push(result[i - 1] + result[i - 2])
    }
    return result[n -1]
}

fibo(50) // 12586269025

오히려 위 방식처럼 반복문을 활용하면 더 빨리 계산되어 출력 결과가 도출 된다.

재귀 베이스에 접근이 오래 걸릴 경우 재귀 함수보다 반복문 for-loop를 사용할 것을 추천한다!!!

---

재귀 함수는 자기 자신을 계속 호출하는 거울 속의 거울과 비슷하다.

재귀 함수 메커니즘 과정을 머릿속으로 생각하는 것이 많이 복잡할 수도 있지만,

잘 활용할수만 있다면 복잡한 로직을 쉽게 풀어낼 수 있을 것이다.