TIL No.14 재귀함수의 활용

😇넋두리

나 같이 실력이 부족한 사람은 본디 의사코드(suedo-code)를 작성하거나, 그림을 그려서 코드가 어떻게 돌아가는지 충분히 생각해보고 코드를 짤 필요가 있는데... 분명 섹션 2가 끝나고 굉장히 자신감있게 시작한 섹션 3인데 너무나도 처참한 몰골이 되어가고있다...(고작 2일이 지났는데 단단한줄 알았던 내 멘탈이 심각하게 부서져있다..ㅋㅋㅋㅋ)

재귀 파트가 앞에 놓여져있는줄 모르고 기본적인 재귀함수에 대해 알고리즘 책을 보면서 며칠전에 공부한터라 약간 자신감이 있었는데...😂(고작 며칠 먼저 본건데 오만하다 오만해;;)

 

분명 쉬운문제들은 금방 이해해서 슥슥 풀리는데 위에 말한대로 조금만 체계적으로 풀려고하면 아직 문제해결의 나만의 공식이 제대로 정립되지않아서 우왕좌왕하는 경우가 꽤 많은 것 같다.

 

✍️오늘의 서술 포인트!!                                                                                                                

 

1. 재귀함수 활용한 문제 2문제 의사코드 작성하며 연결된 개념까지 공부해보기

2. 문제해결능력 향상을 위한 고찰

3. DOM 활용에 대한 복습(이라쓰고 반성이라 읽는다)

 

첫번째 문제

Q1. 피보나치 수열
수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야한다.

 

조건

• 함수는 재귀함수 형태로 작성해야한다.
• 반복문 사용은 금지!!
• 피보나치 수열은 0부터 시작한다.

먼저 의사코드 없이 샤샥하고 작성한 나의 코드로부터 귀납적으로 접근해보자.

function fibonacci(num) {
  // num > num번째 요소
  // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
  // 21 + 34 = 55
  if(num===0) return 0 // 피보나치 첫번째 요소
  if(num===1) return 1 // 두번째 요소

  return fibonacci(num-2) + fibonacci(num-1)
}

 

아무 생각없이 바로 작성하지는 않고 주석 3줄을보면 나름 생각을 하긴 했다...

일단 입력값이 무엇이고 최종적으로 출력해야하는 것이 무엇인지에 대해 num이 입력된 경우 num번째 요소를 출력해야한다는 방향은 잘 잡았다. 그리고서는 초반에 피보나치 수열이 진행되는 상황을 나열해놓고 3번째 줄에는 리턴값이 어떤 형태를 띄어야할지 표시하기 위해 적어놓았다.

21 + 34 => 55 와 같은 답이 리턴되려면 n-2번째 요소와 n-1번째 피보나치 수의 합을 리턴해야한다.

그리하여 return을 적고 함수 fibonacci에 n-2와 n-1을 인자로 전달한 함수를 + 연산자로 둘 다 실행되도록 하였다.

 

이렇게 보면 나름 잘 풀었지만,, 어려운 문제를 만나자마자 바로 바닥이 드러났다. 그래서 이 문제부터 base case, recursive case 이렇게 두 가지로 구분해서 다시 의사코드를 작성해보고 피보나치를 다른 방식으로 풀어서 계산복잡도(big O)를 감소시킬 수 있는 방법이 있는지 알아본 뒤, 더 어려운 문제에도 동일한 방식으로 의사코드를 작성해보겠다.

 

일단, base case란 재귀함수가 실행되는 것이 종료되는 조건으로... 불필요하게 반복된 5,6번째 줄을 압축하면

if(n <= 1) return n;

이렇게 첫번째 요소와 두번째 요소의 값이 입력된 경우 n값을 리턴하며 종료하게 된다.

따라서 fibonacci(0), fibonacci(1) 이렇게 입력되면 0과 1을 리턴하게 된다. 피보나치 수는 이 두 가지만 있으면 뭐든지 만들 수 있다.

 

이제 recursive case 즉, 반복 실행될 코드를 만들어 보자. base case에 도달하기 위해서는 동일한 인자를 리턴하면 안될 것이고 점점 base case에 접근하도록 코드를 짜야한다. 피보나치의 경우 내가 구하고 싶은 값이 10번째라고한다면 10번째는 8번째와 9번째의 합이고 이를 식으로 포현하면 
'함수 fibonacci에 n-2와 n-1을 인자로 전달한 함수'라고 적었던 부분이다.

fibonacci(n) === fibonacci(n-1) + fibonacci(n-2)

fibonacci(10) === fibonacci(9) + fibonacci(8)
fibonacci(9)는 8,7번째 요소의 합으로 나뉘고 8은 6,7번째 요소의 합으로 나뉘므로, 이를 식과 그림으로 표현하면

fibonacci(10) === fibonacci(9) + fibonacci(8) === fibonacci(8) + fibonacci(7) + fibonacci(7) + fibonacci(6) ...

 

 

이렇게 base case가 있는 바닥까지 도달하게 된다.

아무생각없이 짠 4줄의 코드의 작동을 설명하는데 꽤나 복잡한 과정이 필요하다.(사실 보이지 않게 일어나는 자바스크립트의 다른 기능이나 개념들은 훨씬 복잡하므로 이정도면 간단하다고 해야할 것 같다.)

 

다른 풀이법 알아보기

수요일과 목요일에 풀어야하는 코플릿문제와도 연관이 있는데 피보나치 수열의 계산 복잡도를 위와 같은 방식보다 훨씬 줄일 수 있는 다양한 방법에 대해 탐색해보자.

 

1. 동적 계획법에 따른 big-O 줄이기
https://velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

 

2. 꼬리재귀함수

 

꼬리재귀함수에 대해서는 공부도 부족하고 무엇보다도 현재 Javascript에서 사용할 수 없으므로 다음에 기회가되면 다뤄보기로 하고, 동적계획법을 활용하면 한번 계산한 피보나치 수를 기억해가면서 call stack을 줄일 수 있고 이는 계산 복잡도 감소로 이어진다.

 

자세한 코드는 내일 TIL에 동적계획법에 대한 내용과 함께 더 적어보고자 한다.

 

두번째 문제

Q2. flattenArr
다차원 배열을 입력받아 1차원 배열로 변환하여 리턴해야 합니다.

 

조건

• 함수 flattenArr는 재귀함수의 형태로 작성합니다.
• Array Method flat()과 flatMap() 사용은 금지됩니다.
• 반복문(for, while) 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 입력으로 전달되는 다차원 배열이 중첩된 정도(중첩의 깊이)는 정해져 있지 않습니다.
• 빈 배열을 입력받은 경우, 빈 배열을 리턴해야 합니다.

 

의사코드를 작성하기 전에 먼저 문제에 제시된 함수의 이름과 조건을 살펴보면, flat이라는 메소드가 있었다는 사실을 알 수 있다.(나는 몰랐다...)

 

flat은 복사하는 메소드로서 원본을 해치지 않고 ()안에 주어진 전달인자의 값만큼 낮은 차원의 배열을 리턴한다. 자세한 내용은 공식문서에 더 잘 쓰여있다.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flat

Array.prototype.flat() - JavaScript | MDN

우리는 조건에 주어진대로 flat과 flatMap 메서드는 사용하지 않을 것이고, 반복문을 사용하여 해결할 것이다. immutability 역시 지켜야하며 빈 배열을 입력받은 경우 빈 배열을 리턴하는 것까지 고려하여 코드를 작성해야 한다.

 

의사코드

1. 다차원의 배열이 주어지고, 요소 중에도 다차원 배열이 있는 경우도 있는데 각각의 요소의 배열 [ ]를 다 풀고 1차원 배열안에 양의정수들이 나열된 배열을 최종값으로 리턴해야한다.

2. base case는 배열안의 요소 중에 배열이 하나도 없는 경우에 해당 배열을 리턴하면 된다.

3. recursive case는 for 문을 사용하여 배열안의 요소 하나하나를 순회하면서 배열을 만날 경우 배열을 한 차원 낮춘다.

3-2. 다차원 배열을 만난 경우 한번에 0차원 양의정수 요소로 만들어도 되지만 이번에 주어진 테스트 케이스에 따르면 배열이 중첩된 수와 유사하게 함수가 호출되어야하므로 이 방식은 사용하지 않는다.

4. 함수 맨 처음에 빈 배열을 새로운 변수로 선언하고 for문이 다 종료된 후에 빈 배열에 추가된 요소들을 최종적으로 리턴한다.

 

이 때 의문이 드는 지점이 생길 수 있다. 과연 flattenArr() 이 함수는 언제 재귀적으로 호출되어야하는가이다. 이는 생각해보면 단순하다. 어떤 행위를 반복적으로 해서 어떤 상태로 나아가야 하는가를 생각해보면 된다. 배열이 겹겹이 싸여 있는 것을 점점 줄여서 양의정수만 남게 해야한다. 말그대로 recursive case의 반복을 통해 base case에 다다르는 원리를 사용하면 피보나치보다 좀 더 복잡하게 느껴지는 이 문제도 꽤 간단하게 해결할 수 있다.
 recursive case가 for문 안에 있고(정확히는 for문의 일부분이라고 해야겠다.) 배열을 만나면 반복되는 조건이므로 for 문 안에서 순회를 돌고 있는 요소가 배열인지 아닌지에 따라 분기를 나누어주어야하며, 배열인 경우에 다시 함수가 호출되도록 하고 순회를 도는 요소가 전부 양의 정수인 경우 for문이 종료될 수 있도록 하여 for 문 다음에 있는 최종 리턴문이 실행되도록 한다.