재귀 문제풀이 정리1

내가 재귀를 배우면서, 개념이 잘안잡혀 문제를 먼저 풀면 어느정도 익숙해지지 않을까? 하고

맨땅에 헤딩하듯 했는데

 

쉬운 숫자의 덧셈이나 곱셈만 풀뿐 스트링이나 배열,객체 등의 재귀에는 어려움이 있어.

엔지니어분께 다시 개념을 배우고 정리중...

 

내가 재귀를 못풀었던 이유 

- 문제를 쪼개려고만 했었다. 그래서 덧셈이나 곱셉은 쪼개지는데

문자열이나오면.. 어떻게 쪼개라는거야... 이러고 있었음..

- 재귀를 어디서 불러야할지 감이안옴

 

>> 해결방법

- 탈출조건과 반복조건을 명확하게 구분한다

- 탈출조건을 만족해서 빠져나가는 순간이 있어야한다.

- 반복조건에 재귀를 사용한다.

---

문제1) 재귀에서 굉장히 간단한 예로 많이드는 팩토리얼 문제

수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴해야 합니다.

n! 은 1부터 n까지 1씩 증가한 모든 값의 곱입니다.

 

 

주석처리된 부분을 보면 나는 예시로 num이 5일 경우를 생각해

1,2,3,4,5를 계속 곱하는 예를 들어풀었다. 이렇게 예시가 보일경우 간단함.

 

더 자세히 풀어보면

 

문제를 작게 계속 쪼개본다.

5 * 4 * 3 * 2 * 1을 쪼개어

5* (4*3*2*1)
5*4 (3*2*1)
5*4*3 (2*1)
5*4*3*2 (1)

괄호부분을 보면 num에서 -1씩 계속 작아지는 것을 볼 수있다.

그래서 무슨 숫자가 들어와도 함수가 작동하려면
(num -1)이 와야한다.

탈출조건 : num === 0일때 1리턴
반복조건 : (num -1)

**탈출조건은 문제의 주의사항에서 미리주어짐**
(factorial(0)은 1로 정의됩니다.)

 

---

문제2) 배열문제 >head,tail이용하기

수(num)와 배열을 입력받아 차례대로 num개의 요소가 제거된 새로운 배열을 리턴해야 합니다.
 **주의사항**

(num과 arr.length 중 최대값만큼 제거합니다.)

 

배열문제를 풀때는 head와 tail로 나눠서 푸는 방법이 제일 간단하다고한다.

const head = arr[0];

const tail = arr.slice(1);

 

역시나 예시를 하나 만들어 생각해보면, arr = [1,2,3,4,5] num = 2 일때 arr에서 2개가 제거된 [3,4,5]가 나와야한다.

 

탈출조건 : num ===0 이거나 arr이 빈배열일때, return arr; (뺄게없거나, 뺄수있는 배열의 요소가 없으니)

반복조건 : num-1, tail(0번쨰 요소를 뺀 나머지 값)

 

이 탈출조건을 만족시키기위해서

arr에서 요소한개를 제거하면 num에서 -1를뺀다 > 언젠가 num ===0 인순간이 온다.

 

---

더 고난이도의 문제를 풀기위해 구글링해보았을때 forEach가 굉장히 유용하게 쓰여서 정리를 해보고 넘어가자.

 

[MDN참고]

- forEach() 메서드는 주어진 함수를 배열 요소 각각에 대해 실행합니다.

 

배열에서 쓰인다..오호 배열의 각요소에 한번씩 접근하는 문제를 풀때 사용하면 될듯.

다음 재귀 포스팅에서 더고난이도의 재귀문제와 foreach 사용풀이를 가져오겠습니다.

mdn