[재귀] 재귀(Recursion)란?
이번 글에서 재귀함수란 무엇인지 간단히 정의해보고,
다음 게시물부터는 재귀함수에 관한 문제를 쭉 풀어보고자 한다.
재귀란 무엇일까?
- 재귀(Recursion)는 스스로를 부른다는 의미이다.
- 프로그래밍 언어에서는 함수가 자기 자신을 호출한다는 의미가 될 것이다.
재귀는 재귀함수의 형태로 실제로 프로그래밍의 많은 부분을 차지하고있는데,
JSON.parse, JSON.stringify, DOM 순회 등에서 사용이 되며
본인도 재귀함수로 배열 고차함수인 reduce, map, filter, find를 만들어 본 적이 있다.
사용해본 바, 재귀함수는 기능을 작성할 때 편리하고 가독성이 좋아질 수 있는 장점이 있다.
다만 크나 큰 단점도 존재하며, 그 단점은 마지막에 후술한다.
스택 자료구조(콜 스택)
함수가 호출되면 호출된 함수는 콜 스택에 push된다.
스택 자료구조이다보니 TOP 방향에 계속 쌓이게 될 것이다.
자바스크립트에서는 함수가 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에 누적되서 쌓이며,
함수가 사라지지 않는 만큼 함수가 가진 변수나, 함수 그 자체로도 메모리를 차지하여 공간 복잡도가 증가할 수 있다.
따라서 재귀는 비싼 연산이라 할 수 있으며,
편리한 기능이지만 반드시 필요한 곳에 사용해야 한다.