TIL 6월 29일 - Recursion 문제들

꼭 재귀로 풀어야 할까?

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

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

• 여러 재귀 문제들과 케이스를 보면서 고민해봤는데, 케바케가 꽤 심한 것 같았다.
• 약간 감이 오는 중인데, 확실하지가 않다. 그래도 나름의 방법을 만들어 보는 중이다. (저만의 방식입니다.!!)
• 1. 지속적으로 (변하면서) 받는 인자
• 2. 중단조건
• 3. 결과값
     특히 결과값이 어떤지에 따라서 여러 형식으로 나뉘는 것 같다.
     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. 지속적으로 받는 인자 m 과 result
   result는 container느낌으로 추가하는 배열을 계속 받을 기본 배열이다.
   m은 0부터 늘어나면서 n에 도달하면 함수가 멈춘다.

   • 주의할 점은 m과 result는 함수가 '맨처음' 실행될때만 초기화 시켜줘야 한다는 점이다.

2. 중단조건 : m이 n에 도달하면 멈춘다.

3. 결과값 : 배열 (누적된), 여기서는 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;
    }
}

}