IMMERSIVE

재귀함수(Recursion, recursive function)

Recursion은 Data structure라고 할수는 없지만, 함께 이해하기 좋은 개념입니다.

1. 들어가기전에 About JavaScript

callstack

자바스크립트는 싱글스레드 프로그래밍 언어이다.
이는 싱글 스레드 런타임(실행환경)을 가지고 있다는 말인데, 한번에 하나의 싱글 콜스택만을 가지고 있다는 말이다.
하나의 프로스램은 동시에 하나의 코드만 실행할 수 있다고 생각하면 된다.
콜 스택은 기본적으로 자료구조로 실행되는 순서를 기억하고 있다.
함수가 실행하려면 스택에 해당하는 함수를 집어넣고, 함수에서 리턴이 일어나면 스택의 가장 위쪽에서 해당 함수를 제거한다.
이것이 기본적인 자바스크립트 실행 구조이다

CallStack 천천히보기

stack1 stack2 stack3 stack4 stack5 stack6 stack7 stack8 stack9

2. 재귀함수란?

**재귀함수(Recursion)**는 어떤 함수를 정의할 때, 그 함수 자체를 재참조하는 함수를 말합니다.

recusive

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.

"재귀함수가 뭔가요?"

잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.

"재귀함수가 뭔가요?"

잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...

recusive

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.
재귀함수란, 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 방식으로 문제를 해결하는 방법이다. 재귀 호출이나 되부름 이라고 불리기도 한다.(재귀함수)
재귀함수가 쓰이는 곳에서는 매 호출마다 입력값(파라미터)이 변한다. 입력값의 변화가 없거나 특정 패턴을 반복하게되면 그 재귀함수는 영원히 반복되다가 콜스택(Call Stack) 초과로 프로그램에 과부하가 생긴다.
보통 재귀는 문제를 해결하기 위해 초기 문제의 범위보다 약간 족읍 하위 문제를 해결하며 답을 찾아간다.
하위 문제의 끝에는 종료 조건(base case)을 넣어줘서 무한반복을 막고, 값이 출력되도록 설정해야 한다.

3. 장점

반복문을 대신하기 때문에 코드가 간결해진다(간격한 코드)
가독성
잘만 사용하면 빠르다.

4. 단점

코드가 커지면 코드 파악 및 문제를 발견하기 어려움
메모리 사용량
어렵다

5. 사용

컴퓨터 기본 자료구조 해결에 사용
프로그램을 만들 때 자료구조의 개념이 사용됨

6. 코드

아래의 간단한 예제 코드를 봅시다.

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

만약, *factorial(5)*를 실행한다면 결과값으로 *5 * factorial(4)*를 반환하고,

*factorial(4)*는 *4 * factorial(3)*이 반환됩니다.

*factorial(3)*은 *3 * factorial(2)*가 되고,

*factorial(2)*는 *2 * factorial(1)*이 되는데,

이때 *factorial(1)*의 결과값이 1이므로

최종적으로 *5 * (4 * (3 * (2 * (1))))*과 같이 됩니다.

위와 같이 함수 자체를 다시 한번 실행하는 함수를 *재귀함수(Recursion)*라고 합니다. 재귀함수는 알고리즘을 수식(특히, 점화식 형태의 수식) 그대로 코드로 작성할 때 많이 사용합니다. 그만큼 직관적이고 가독성이 높다는 장점이 있죠. 하지만 연산이 많아지면 Stack Overflow가 발생할 수 있습니다.