[알고리즘] 자기 자신을 호출하는 , 재귀

프론트엔드 부트캠프를 수강하면서 알고리즘을 하나씩 풀어나가다 커다란 벽을 만났다.

자기자신을 호출하는 개념인 재귀인데, 재귀의 개념을 이해하는데는 그리 어려움이 없었지만 재귀를 이용해서 알고리즘 문제를 푸는데 애를 먹고있다.

 

---

재귀를 사용하기 좋은 경우

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

극단적으로 중첩된 반복문의 예시, 이럴경우 유지보수도 어렵고 코드를 이해하기도 힘들다

 

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 

반복문(for문,while)은 재귀로 나타낼 수 있고, 또 재귀는 반복문으로 나타낼 수 있다. 재귀를 사용하는게 더 가독성이 좋고 간결한 경우도있고, 반복문 사용이 더 쉽고 간결한 경우도 있으니 상황에 맞추어 잘 구분해 사용 할 수 있어야하고, 그렇기 위해선 많은 문제를 풀어봐야한다.

 

---

재귀함수의 기본적인 형태

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

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

재귀함수는 문제를 탈출하는 조건(Base case)을 정확히 명시해주어야한다. 재귀함수를 자칫 잘못 사용하면 무한루프에 빠지게되어 작동을 정지하게 된다. (처음 재귀를 접하다보면 무조건 겪게될 상황)

 

---

예시 문제

배열을 입력받아 모든 요소의 곱을 리턴해야 한다.

 

function arrProduct(arr) {
  let n = arr.length
  // base case (탈출조건)
  if(arr.length<1){
    return 1
    
 // recursive case (재귀부분)
  }else{
    return arr[0]*arrProduct(arr.slice(1))
  }
}

위와 같이 나타낼 수 있다. 입력받은 arr의 length가 1보다 작을때, 즉 arr의 요소가 더이상 없을때는 1을 리턴하고, 그 외의 케이스에서는 지속적으로 자기자신에 arr요소를 하나씩 뺀 함수를 호출하게된다.