코드스테이츠 Pre-course를 시작한지 5주가 지나 6주의 끝을 향해 가고 있다. 원래 스케줄을 총 10주이지만 조기수료 와 가장 가까운 Immersive course 신청을 맞추기 위해 6주안에 커리큘럼을 끝내야 했다. 어려운 과제를 만날때마다 절망스러웠지만 이 방대한 인터넷의 이름없는 스승님들 덕분에 겨우겨우 끝마칠 수 있었다. 이제 가장 중요한 건 지금까지 배운것들을 복습하고 또 복습하며 온전히 내 것으로 만드는 일이 될 것 같다.
오늘 쓰려는 글은 가장 최근 과제의 주제였던 Recursion 이다. 편리하지만 가장 까다로운 방식으로 느껴져서 개인적으로 기피하면서도 공부가 필요하다고 느끼는 방식이다.
그렇다면 Recursion 이란 무엇일까?
1. What is Recursion?
Recursion은 한국어로는 “재귀” 라는 뜻인데 사전을 찾아보면 ‘본디의 곳으로 다시 돌아오는 것' 이라고 설명되어 있다.
이 재귀 용법이란 것이 컴퓨터공학에서 쓰이는 방식은 바로 함수가 스스로를 다시 호출(call) 하는 식으로 이 함수는 어떠한 조건을 마주칠 때까지 계속 반복하게 된다. 이 조건을 “Base case” 라고 부르며 말 그대로 ‘기초가 되는 경우/조건' 을 뜻한다. Base case 가 제대로 설정되어 있지 않으면, 함수가 스스로를 계속 호출하며 무한 루프에 빠질 수도 있기 때문에 재귀 용법에서 매우 중요한 부분이다.
1-1. Factorial
Recursion 을 설명할 때 가장 많이 이용되는 사례를 보면 팩토리얼(Factorial)이 있다.
예를 들어, 수학에서 4! 라는 표현은 4 * 3 * 2 * 1 = 24 이며, 4 자신부터 1까지 순차적으로 곱해준 값을 의미한다. 재귀용법을 이용해 표현하자면 아래처럼 되겠다.
4! = 4 * 3!
4! = 4 * 3 * 2!
4! = 4 * 3 * 2 * 1즉, 아래와 같은 공식을 가지고 있다는 뜻이 된다.
n! = n * (n-1)!
이것을 이용하여 주어진 수의 팩토리얼 값을 리턴하는 함수를 만들어보면 아래와 같다.
function factorial(num) { //if num = 4; (a)
if ( n === 1) { //if factorial(1), n === 1 (c)
return 1;
} else {
return n * factorial(n-1); // return 4 * fatorial(3) (b)
}
}수가 1보다 클 경우엔 (a) -> (b) 의 과정을 반복하다 결국 (c)라는 Base case 에 도달하게 된다.
함수가 Base case 에 도달하게 되면 값의 반환은 함수가 안으로 호출된 것과 반대로, 가장 최근의 값부터 가장 나중에 호출된 값으로 거슬러 올라가게 되는데 이것은 자바스크립트(또는 여러 언어들)의 함수 호출 방식 “Call Stack” 과 관련이 있다.
1-2. Call Stack
일단 Stack 이란 것은 자료구조의 개념 중 하나로, 쉽게 표현하자면 입구만 존재하는 상자 혹은 터널 (혹은 Array)이라고 생각하면 쉽다. 만약 알파벳 카드를 A 부터 Z 의 순서대로 상자에 넣었을 때, A 를 꺼내려면 가장 위의 카드 Z 부터 다시 꺼내야 가장 밑의 A에 도달할 수 있다.
자바스크립트에서도 함수가 호출(call)되면 Call Stack 이란 곳에 쌓이게(push) 되고 출력되면 stack에서 빠져나오게(pop)된다.
재귀가 일어날때마다 함수는 Call Stack에 쌓이게 되는데, 만약 Base case가 제대로 설정되어 있지 않다면 함수는 Call Stack의 한계를 넘어설만큼 호출이 될테고, 이러한 현상을 “Stackoverflow”(또는 우리의 구원자) 라고 부른다.
다시 위의 팩토리얼 예시로 돌아오면, 다행히 우리의 함수는 (c)라는 Base case를 만나 1 * 2 * 3 *4 = 24라는 값을 무사히 리턴하게 된다. 그렇기에 개인적으로 재귀 용법을 사용할 때는 이 Base case의 설정이 반 정도의 중요도를 차지한다고 생각되었다.
이 재귀 용법은 “for 문” 처럼 모든 속성을 iterate 하는 성격이 있어서 잘 사용하면 반복문을 간결한 코드로 표현할 수 있다는 장점이 있다. 또한 “Tree” 형식처럼 여러 가지가 딸린 형식 또한 재귀를 통해 간단히 확인할 수 있다.
단점 또한 존재하는데, 바로 위의 말했던 Call Stack과 관련이 있다. 이 Call Stack 은 넣거나 호출하거나 한 번에 한가지의 행동만 가능하기 때문에, 다뤄지는 데이터의 용량이 크다면 최종적으로 값이 리턴되기 전까지 수많은 call들이 stack안에 존재할 수 밖에 없다.
이렇게 재귀 용법을 상황에 맞게, 올바른 조건으로 작성한다면 훨씬 간단명료한 코드를 작성할 수 있게 된다. 그리고 그 이야기는 곧 문제를 통찰하는 능력 또한 기를 수 있다는 뜻이 될 수 있다.
오늘은 Recursion에 대해 글을 써보았는데 나 스스로도 글을 쓰며 조금은 정리가 된 것 같은 느낌이 들어 그나마 다행이라 느낀다. Pre-course 수료하기 전까지 지금까지 배운 개념들을 오늘처럼 다시 글로 설명하고 응용하는 시간을 가져야겠다는 생각이 들었다. 그렇게 되면 조금은 더 나은 코드를 작성할 수 있겠지. 지루한 글을 여기까지 읽어주신 분이 있다면 감사하다는 말을 드리며, 오늘은 여기까지.
