꼭 재귀로 풀어야 할까?

  • 어떤 문제를 재귀로 풀어야하는 경우를 계속 마주하게 됐다.
  • 힘들었던 점은 왜 굳이 재귀로 풀어야하는지 모르겠는 경우들이 있다는 점인데, 여러 코드들도 비교해보고 검색도 해보니 이 의문이 맞는 의문이었다. 재귀가 필요하지 않다고 느껴지면 재귀를 쓰지 않아야 한다.
    다만 그럼 필요할 때는? 이미 재귀적으로 잘 쓰이고 있는 코드를 들여다봐야 할때도 있을 것이고.. 지금 여러 문제를 재귀로 풀어보는건 해당 문제에서 재귀가 필수라서라기보다는 이런때들을 위해 연습을 하는 느낌이다. 만들어보고 생각도 해봐야 언제 필요하고 유용한지 알 수 있을 것이다.
  • 예를들어 factorial이나 fibonacci는 분명히 재귀가 필수인 문제들이다. 그리고 그 외로 개인적으로 for문이 4번이상 중첩되는 코드를 보면 아무래도 가독성이 떨어진다. 만약 for문의 중첩이 점점 늘어난다면 거의 해석 불가능의 코드가 될 것이다. 이때도 재귀가 필수가 될 것이다.

재귀 함수를 만들때 원칙이 있다면 뭐가 있을까?

  • 여러 재귀 문제들과 케이스를 보면서 고민해봤는데, 케바케가 꽤 심한 것 같았다.
  • 약간 감이 오는 중인데, 확실하지가 않다. 그래도 나름의 방법을 만들어 보는 중이다. (저만의 방식입니다.!!)
    1. 지속적으로 (변하면서) 받는 인자
    1. 중단조건
    1. 결과값
      특히 결과값이 어떤지에 따라서 여러 형식으로 나뉘는 것 같다.
      3-1. primitive value, object를 반환
      3-2. primitive value (누적)
      3-3. object (누적)

factorial

factorial을 예로 들어보자.
코드로 function factorial(n) { ... } 을 만들어야 한다.

  1. 지속적으로 (변하면서) 받는 인자는 n이고
  2. n에 0이 들어오면 중단하고 1을 반환한다.
  3. 결과값은 이전까지의 factorial의 값과 n을 곱해준 number이다.

코드로 짜보면 아래와 같을 것이다.

function factorial(n) {
  if(n === 0){
      return 1
  }else{
      return n * factorial(n - 1);
  }
}

위에서 포인트는 return으로 n에다가 factorial(n-1)을 그대로 곱해서 반환한다는 점이다.
이게 가능한 이유는 factorial이 number를 반환하기 때문이다.

만약 factorial이 중단지점에서 object를 반환하는 함수라고 생각해보자.
그럼 factorial(n-1)에 n을 곱해서 반환하는 형식을 취한다는 것은 말이 안되는 발상이다.

말을 한김에 factorial이 배열을 반환하는데, 배열의 각 요소는 factorial(n)까지의 값을 담은 또다른 배열이라고 해보자

예시)
factorial(0) = [[1]]
factorial(1) = [[1], [1]]
factorial(5) = [[1], [1], [2], [6], [24], [120]]

변형 factorial

원래 factorial code

function factorial(n) {
  ifn === 0){
      return 1
  }else{
      return n * factorial(n - 1);
  }
}

위와같은 기본 코드를 보면 조금 황망한데

  • 결과값으로 이젠 배열을 반환해야 하고, factorial(n-1), factorial(n-2)로 가면서 기존 배열에 누적을 시켜줘야 하기 때문에 n * factorial(n-1) 로 결과값을 반환하는건 안되기 때문에 복잡해질 것이기 때문이다.

마음으로는 기본 배열이 있고, 이 배열에 factorial이 0부터 시작되면서 n까지 가면서 얻은 값을 추가해주다가, n에 도달하면 중단하고 그 전까지 누적된 배열을 반환하면 편할 것 같다. 사실 이걸 그냥 구현해주면 된다.

  1. 지속적으로 받는 인자를 바꾸고 (어떤 값이 들어와서 0에서부터 n까지 점점 늘어나야한다.)
  2. 중단조건을 바꾸고 (어떤 값이 n에 도달했을 때)
  3. push가 계속되는 기본 배열을 반환해야 한다.
    3-1. 이 배열은 근데 맨 처음실행될때 말고는 초기화 되면 안된다.

포인트는 인자를 추가해주는 것이다.
function factorial2(n, m, result){...}
위와같은 형식으로 바꾸고 result에 누적한 배열을 계속 전달하면서 다음 함수를 호출해줄 것이다.

  1. 지속적으로 받는 인자 mresult
    result는 container느낌으로 추가하는 배열을 계속 받을 기본 배열이다.
    m은 0부터 늘어나면서 n에 도달하면 함수가 멈춘다.
    • 주의할 점은 m과 result는 함수가 '맨처음' 실행될때만 초기화 시켜줘야 한다는 점이다.
  1. 중단조건 : m이 n에 도달하면 멈춘다.

  2. 결과값 : 배열 (누적된), 여기서는 result일 것이다.

function factorial2(n, m, result){
  m = m || 0;
  result = result || [];
    // 함수가 맨 처음 실행될때는 undefined이므로 위와같이 초기화가 된다.
  if(m === 0){
    result.push([1]);
  }else{
    let beforeArrayLength = result.length;
    let beforeValue = result[beforeArrayLength-1][0];

    result.push([m * beforeValue]);
  }

  if(n === m){
    return result;
  }else{
    return factorial2(n, m+1, result);
  }
}

factorial(5) // [ [ 1 ], [ 1 ], [ 2 ], [ 6 ], [ 24 ], [ 120 ] ]

그래서 위와같이 만들어주면 된다.

_.flatten

n = function(nestedArray, result) {
  result = result || [];

  for(let val of nestedArray){
    if(Array.isArray(val)){
      _.flatten(val, result);
    }else{
      result.push(val);
    }
  }

  return result;
};

fibonacci

  1. 지속적으로 (변하면서) 받는 인자는 n

  2. 중단조건은 number가 1이하가 들어오는 상황이다.
    2-1. fibonacci수열의 기본은 0, 1로 시작해서 값들의 누적이므로.
    fibonacci는 return으로 함수 2개를 호출한다.
    따라서 fibonacci(2)은 fibonacci(1)와 fibonacci(0)을 호출한다.
    그래서 fibonacci(1)와 fibonacci(0)일때 2가지를 기본으로 해준다.

  3. 결과값은 number인데, 이전의 결과들이 중첩(합)돼야한다.
    3-1. number는 어딘가에 담을 필요 없이 결과값을 계속 누적시켜줄 수 있으므로
    3-2. return값을 계속 더해주면 된다.

function fibonacci(n){
  if(n === 0){
      return 0;
  }

  if(n === 1){
      return 1;
  }

  if(n >= 2){
      return fibonacci(n-1) + fibonacci(n-2);
  }
}

아래 modulo 부터는 작성하다 말았다.


modulo

function modulo(value, divider){

}
// 1. 인자로는 지속적으로 숫자만 들어온다. 
//   - (value로 새로운 값이 지속적으로 들어오는 형태)
//   - 인자type에 따라 함수의 행동이 달라지지 않는다.
// 
// 2. 중단조건
//   - value의 절대값이 divider보다 작아지는 경우 중단한다.
// 
// 3. return값
//   - 중단한 뒤의 value값을 반환한다.
// 
// 4. 기타 조건들
//   - 여기서는 원래의 value에 따라서 결과 값이 달라진다.
//   - 기타 조건때문에 parameter를 3개로 받으면 어떨까 싶다.
//   - divider가 0일때 NaN을 return해야한다

function modulo(value, divider, isPositive){
  if(divider === 0) return NaN;
  isPositive = isPositive || (value < 0 ? false  : true)

  if(Math.abs(value) < Math.abs(divider)){
    let result = (isPositive ? value : -value)
    return result;
  }

  return modulo(Math.abs(value) - Math.abs(divider), Math.abs(divider), isPositive);
}

예시문제 1. id 를 이용하여, 해당 객체를 찾아내는 문제

    let data = [
        { id: 1 },
        { id: 2 },
        { id: 3 },
        { id: 4, children: [
            { id: 6 },
            { id: 7, children: [
                { id: 8 },
                { id: 9 }
            ]}
        ]},
        { id: 5 }
    ]

    findObjectById(6) // { id: 6 }
    findObjectById(7) // { id: 7, children: [{id:8}, {id:9}] }

    findObjectById(number){

    }

예시문제 2. name을 통해 해당 객체를 찾아내는 문제

var data = [ 
            { 
              "type": "folder",
              "name": "animals",
              "path": "/animals",
              "children": [ 
                  {
                    "type": "folder",
                    "name": "cat",
                    "path": "/animals/cat",
                    "children": [
                      {
                        "type": "folder",
                        "name": "images",
                        "path": "/animals/cat/images",
                        "children": [
                          { 
                            "type": "file",
                            "name": "cat001.jpg",
                            "path": "/animals/cat/images/cat001.jpg"
                          }, {
                              "type": "file",
                              "name": "cat002.jpg",
                              "path": "/animals/cat/images/cat002.jpg"
                          }
                        ]
                      }
                    ]
                  }
                ]
            }
        ]

예시 : 
findByFileName('cat002.jpg') 
--> {
  "type": "file",
  "name": "cat002.jpg",
  "path": "/animals/cat/images/cat002.jpg"
}
---------------

function findByFileName(name){

}

// 함수가 위와같을 때
// 1. 인자값으로 지속적으로 name만 받는다.
//   ( 인자로 지속적으로 변형되어 들어오는 값은 없음 )
//
// 2. 중단조건 : 해당하는 name을 찾으면 그때의 객체를 반환한다.
//
// 3. 결과값
//   객체이지만 flatten느낌으로 누적시킬 필요는 없다. 
//   찾았을 때 해당하는 객체를 바로 반환해주면 된다.
//
//   문제는 찾았을 때 해당하는 객체를 반환하는걸 '재귀적'으로 하려면 
//   findByFileName함수만 있으면 어렵다는 점이다.
//   탐색할 객체를 넘겨받아주는게 필요하다. 
//
//

function findByFileName(name){
    let result

    for(let val of data){
        if(val.name === name){
            result = val;
        }
    }
}