[재귀] 재귀(Recursion)란?

이번 글에서 재귀함수란 무엇인지 간단히 정의해보고,

다음 게시물부터는 재귀함수에 관한 문제를 쭉 풀어보고자 한다.

 

 

재귀란 무엇일까?

- 재귀(Recursion)는 스스로를 부른다는 의미이다.

- 프로그래밍 언어에서는 함수가 자기 자신을 호출한다는 의미가 될 것이다.

---

재귀는 재귀함수의 형태로 실제로 프로그래밍의 많은 부분을 차지하고있는데,

JSON.parse, JSON.stringify, DOM 순회 등에서 사용이 되며

본인도 재귀함수로 배열 고차함수인 reduce, map, filter, find를 만들어 본 적이 있다.

사용해본 바, 재귀함수는 기능을 작성할 때 편리하고 가독성이 좋아질 수 있는 장점이 있다.

다만 크나 큰 단점도 존재하며, 그 단점은 마지막에 후술한다.

 

---

스택 자료구조(콜 스택)

함수가 호출되면 호출된 함수는 콜 스택에 push된다.

스택 자료구조이다보니 TOP 방향에 계속 쌓이게 될 것이다.

자바스크립트에서는 함수가 return되거나, 함수의 끝 부분에 도달한다면 컴파일러가 콜스택에 존재하는

호출된 함수를 POP해서 콜스택에서 제거한다.

 

함수가 호출되면 콜 스택에 push되고, return을 만나거나 함수가 쭉 읽혀 종료되면 컴파일러는 콜 스택에서 함수를 POP한다.

 

---

재귀함수(Recursive function)란 무엇인가?

위에서 재귀란 자기 자신을 호출하는 것 이라고 했다.

재귀함수는 의미 그대로 자기 자신을 호출하는 함수이다.

 

프로그래밍에서 재귀함수는 2가지 필수 사항이 있는데

• 컨디션이 끝날 조건(Base case)
• 계속 달라지는 input값 이다.

즉, 매번 달라지는 데이터를 가지고 동일한 함수를 호출시켜 특정 조건에 끝내야한다.

그렇지 않다면 콜 스택에는 무한히 함수가 쌓이다 에러가 나게 된다.

 

---

재귀함수와 콜스택

재귀함수는 자기 자신을 계속 호출하는 함수이다.

즉 함수를 호출하므로 콜스택에 자기 자신을 호출한 값이 계속 쌓게 한다.

 

여기 아래에 1부터 n만큼의 값을 더하는 재귀함수를 놓고 이해해보자.

function sum(n) {
    if (n === 1) return 1
    return n + sum(n - 1)
}

sum(5)

sum은 5를 인수로 받고 실행이 된다.

이 때 n은 1이 아니므로 if문을 건너뛰고

아래 return n + sum(n - 1)이 리턴되는데

sum 함수는 자기 자신이다.

즉 자기 자신이 콜스택에 쌓인다.

 

이를 구글 개발자도구로 보면 아래와 같다.

디버그의 Call stack 부분을 잘 보면 된다.

 

 

위 영상에서 볼 수 있듯이

재귀함수는 Call stack에 누적되서 쌓이며,

함수가 사라지지 않는 만큼 함수가 가진 변수나, 함수 그 자체로도 메모리를 차지하여 공간 복잡도가 증가할 수 있다.

 

 

따라서 재귀는 비싼 연산이라 할 수 있으며,

편리한 기능이지만 반드시 필요한 곳에 사용해야 한다.