TIL 21.05.11

Jaemin Jung·2021년 5월 11일

Today I Learned

목록 보기

16/62

오늘한일

오늘은 재귀함수를 배웠다.
이전에 배웠던 개념들이 짬뽕된 반복문 상위클래스 느낌이다.
다행히 클로저나 고차함수등을 잘 이해하고있어서 개념에대해 설명을 들을때는
이해가 잘 되었다. 코플릿 알고리즘을 풀때도 처음에는 익숙치않아 길을 잃었지만,
그래도 페어와 소통하며 끝까지 풀어냈다.
하지만 toy알고리즘은 쉽지 않았다. 문제 자체도 이해를 하지 못해서..
재귀함수를 이해하고 다시 풀어보려 했으나 또 코드 한줄을 못써봤다.
재귀적 사고가 익숙해지면 다시 도전해볼것이다.

Achievement Goals

(이해한대로 작성하였기에 틀릴수도 있습니다. 계속 공부하며 수정해 나가겠습니다.)

재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
재귀를 언제 사용해야 하는지 알고 있다.
재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.
깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.

재귀 함수 (recursion)

재귀함수는 함수가 특정 조건이 될때까지
자기 자신을 리턴하여 되풀이 하는 함수이다.
재귀란 큰 목표 작업을 간단한 작업 여러 개로 나눌 수 있을 때
유용한 프로그래밍 패턴으로 쉽게 말하면
'비슷한 경우의 문제를 쪼개어서 생각하는 것'이다.
재귀함수는 반복문과 비슷하다고 생각할 수 있다.
재귀함수로 짜여진 코드들은 실제로 반복문으로 대체가 가능하다.
그렇다면 왜 재귀함수를 써야할까?

재귀함수를 사용하는 이유

만약 숫자의 요소로 구성된 배열의 요소의 합을 구하는 공식이 있다면
이는 반복문으로 쉽게 구성이 가능할것이다.

let numArray = [1, 2, 3, 4];
let result = 0;
function sumToArr (arr) {
	for (let i = 0; i<arr.length; i++){
    	result += arr[i];
    }
return result;
}

sumToArr(numArray) // outPut --> 10

그런데 만약 이 배열이 이차원 배열이라면? for문을 겹겹이 사용하면 된다.
하지만 이차원을 넘어 다차원 배열(multi-dimensional array)이라면?
몇차원인지 알 수 없다면? for문으로써는 감당하기 힘들어질 것이다.
어찌 저찌 for문으로 코딩한다해도 코드가 매우 복잡해지고 길어질것이다.

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

이러한 극악의 상황에서 필요한것이 재귀함수이다.
재귀함수는 특정한 조건이 될때까지 함수 본인을 리턴하여 끝없이 반복하기에
한번의 코드로 여러번 되풀이할 수있는 효과가 있다.
주의할점은 특정한 조건(탈출 조건)을 잘 작성하지 못했다면, 무한 루프가 생길 수 있다.

만약 다차원 배열 코드에서 재귀함수를 이용해 끝을 알 수 없는 중첩 단계까지 깊이 파고 들려면,
요소가 배열인 조건일때 재귀호출을하여 쉽게 접근이 가능하다.

재귀함수 사용

재귀함수를 사용하기 좋은 예제를 들자면, 팩토리얼(factorial)이다.
팩토리얼은 n이 하나의 자연수일 때,
1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다.
즉, factorial(3)은 1 x 2 x 3 인 6이다.
재귀함수는 이 문제에 대해서 작은단위로 쪼개 하나씩 해결해나간다.
factorial을 재귀함수를 이용해 코딩해보면..

function factorial(n) {
    if(n <= 1) { // 문제를 더 이상 쪼갤 수 없을 경우
        return 1;
    }//그렇지 않은경우에는
    return n* factorial(n - 1); // 더 작은단위의 문제로 쪼개기
  	//(자기자신 호출)
}
factorial(3); //outPut --> 6

팩토리얼함수에 3의 값을 넣었을 때 처음 스택 3이 쌓이고
두 번째는 3에서 1을 뺀 2, 마지막 탈출조건을 끝으로 1이 쌓인다.
결과적으로 3 x 2 x 1 = 6이 된다.
만약 n이 0이될때까지 쪼갠다면 0은 모든수를 곱했을때 값이 0이기에 문제가 생긴다.
그래서 n을 1에서 멈추게 하였다.

재귀 함수의 기본 구성

재귀의 베이스(base case)
더이상 쪼갤 수 없는 명확한 결과값을 제시하는 경우 (탈출 조건)
재귀 단계(recursive case = recursive step)
목표 작업을 위해 재귀의 베이스에 도달할 때까지 이어지는 동작 (재귀 호출)
재귀 함수의 기본 구성

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}