카테고리 없음

재귀(Recursion)

onys 2021. 6. 8. 19:32
반응형

짝수만 있는 배열을 갖고 오면 돈을 많이 준다고 했나봄.

그래서 마틴이 용을 찾아감.

 

마틴 : 이 배열 중에 홀수 있니? [2, 4, 6, 8]

화난 용 : 처음 숫자만 알려줄거야

마틴 : 아니 홀수 하나라도 있는지 알아야되는데;

 

마틴 : 이거 처음거 홀수임? [2, 4, 6, 8]

용 : 아니?

 

마틴 : (이거 빼고), [4, 6, 8] 이거 처음거 홀수임?

용 : 아니

 

...

 

마틴 : (빈 배열) 이거 홀수임?

용 : 아니

 

마틴 : 오 그럼 여기 홀수는 없는거구나

용 : 난 그런 말 한적 없는데?(츤츤)

 

이게 재귀랍니다. ㅎ.ㅎ

 

재귀(Recursion)

 

이번 포스트에서 배울 목표!

- 재귀가 무엇인지, 그게 어떻게 쓰이는지

- 재귀함수에서 두 개의 필수적인 요소

- call스택을 시각화 하고 재귀 함수 이해하기

- 헬퍼함수 재귀 그리고 순수한 재귀를 이용해서 문제 풀기

 

랍니다~!

 

재귀가 뭔가요?

자기 자신을 call하는 progress(여기에선 함수)

재귀는 왜 쓰는거에요?

재귀는 어디에나 있다.

JSON.parse / JSON.stringify

document.getElementById and DOM traversal(트리순회) 알고리즘

Object traversal(트리 순회)

iteration의 더 깔끔한 대체재가 될 수 있다.

 

 

여기서 잠깐! function이 call될 때 Javascript에선 어떤 일이 일어날까요?

call stack을 만나봅시다.

call stack

은 stack 자료구조에요!

함수가 호출될때마다 call stack의 맨 위로 위치해요

Javascript가 키워드를 return하거나 함수가 끝이 날 때, 컴파일러는 그걸 지워요. 

 

우리가 재귀함수를 쓸 때 새 함수를 계속해서 Call stack에 푸쉬합니다.

그게 언제 멈추는지 우린 어떻게 알 수 있을까요?

 

재귀함수의  필수적인 요소 2가지!

Base Case

재귀가 끝나는 조건

Different Input

항상 다른 인자가 함수에 들어가야 무한루프를 피할 수 있겠죠?

 

function countDown(num) {
  if(num <= 0) {
    console.log("All done!");
    return;
  }
  console.log(num);
  num--;
  countDown(num);
}

// print 3
// countDown(2)
// print 2
// countDown(1)
// print 1
// countDown(0)
// print "All done!"

1씩 작아지는 num을 print하는 재귀함수입니다.

 

function sumRange(num) {
  if(num === 1) return 1;
  return num + sumRange(num-1);
}

sumRange(3)
  return 3 + sumRange(2)
               return 2 + sumRange(1)
                            return 1;

1부터 num까지 더하는 재귀함수입니다.

 

function factorial(num) {
  let total = 1;
  for(let i = num; i > 0; i--) {
    total *= i
  }
  return total;
}

for문을 이용한 factorial 함수입니다.

 

function factorial(num) {
  if(num === 1) return 1;
  return num * factorial(num-1);
}

재귀를 이용한 factorial 함수입니다.

 

재귀에 실패할 때

- Base Case가 없거나 잘못되었을 때

-  return이 없거나 잘못되었을 때

 

멈추지 않아요~! (feat: Stack overflow)

 

헬퍼함수 재귀라는 디자인 패턴을 알아볼거에요

function collectOdds(arr) {
  let result = [];

  function helper(helperInput) {
    if (helperInput.length === 0) {
      return;
    }
    
    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0])
    }
    
    helper(helperInput.slice(1))
  }
  
  helper(arr)
  
  return result;
}

collectOdds([1,2,3,4,5,6,7,8,9])
// [3,5,7,9]

helper함수가 재귀를 실행하고,
실행할 때마다 얻어지는 값을 helper함수 밖의 배열에 저장하는 패턴입니다.

 

pure recursion

function collectOdds(arr) {
  let newArr = [];
  
  if(arr.length === 0) {
    return newArr;
  }
  
  if(arr[0] % 2 !== 0) {
    newArr.push(arr[0]);
  }
  
  newArr = newArr.concat(collectOddValues(arr.slice(1)));
  return newArr;
}

collectOdds([1,2,3,4,5])
[1].concat(collectOdds[2,3,4,5]) // 아무것도 안함.
                [].concat(collectOddValues([3,4,5]))
                                  [3].concat(collectOdds([4,5]))
                                                 [].concat(collectOdds[5])
                                                               [5].concat([])

concat은 배열을 붙여주는 배열메서드입니다.

맨 끝의 [5].concat([])는 [5]가 됩니다.

헬퍼함수와 외부 저장용 변수를 사용하지 않고 한번에 하나의 배열을 얻는 방법이네요.

 

반응형