[Today I Learned] EP.2 재귀

재귀(Recursion)?

재귀(recursion)은 하나의 문제가 있을때 그 문제를 동일한 구조의 더 작은 문제로 나눌 수 있고, 작은 문제를 해결함으로써 전체 문제를 해결하는 방법이다.

재귀적으로 사고하는 법?

4가지로 생각해보는데.. 사실이해가 안되지만 계속해서 이해해봐야겠다.

1. 잘게 쪼개서 생각하기.
2. 재귀적으로 생각하기.
3. 함수 자신의 재귀적인 호출
4. 탈출 조건

어떻게???

요소가 숫자인 배열이 있다고 해보자

const arr = [1,2,3,4]

그러면 이 배열 요소들을 더하는 함수를 만들자라고 한다면 당연히
(작성자는 화살표함수 좋아해서 화살표 함수를 작성하는점 양해..)

const arraySum = ((arr)=>{
	let sum = 0
    let i;
    for(i = 0; i<arr.length;i++){
    sum += arr[i];
    }
    return sum;
    })

이렇게 쓸것이다.

잘게 쪼개어 생각하기

arraySum([1,2,3,4]) = 10 + arraySum([2,3,4])

위에 배열을 하나의 용이라고 치면
0번째 부분을 머리로 치고 나머지 요소를 꼬리 부분이라고 하자

머리부터 꼬리까지 잘게 쪼개어 보면

arraySum([2,3,4]) = 2 + arraySum([3,4]);
arraySum([3,4]) = 3 + arraySum([4]);
arraySum([4]) = 4+arraySum([]);

이렇게 되고 거꾸로 다시 생각해보면 된다.

// 한가지 빈배열을 담는 보조변수를 만든다.
// 빈배열을 담은 보조 변수에 요소하나를 추가한다.(arr.push()같은 느낌)
// 그리고 다른 요소를 arr.unshift()를 하나씩 해준다. 

라고 하면 될꺼 같다.

내가 쓴글은 당연히 배운 것을 내 주관적으로 정리하는 부분이지만
더 정확하게는 요 영상을 참고하면 될꺼 같다.
(이미지를 클릭하면 재귀에 관한 해당 영상을 볼수 있다)