재귀함수?
재귀함수란 자기 자신을 호출하는 함수를 말한다.
종료 조건이 충족될 때까지 반복적으로 스스로를 불러내면서 주어진 작업을 수행한다.
기본구조
function recursiveFunction() {
// 종료 조건(Base case): 재귀를 멈추는 조건
if (종료 조건) {
return 결과;
}
// 재귀 호출(Recursive case): 자기 자신을 호출
recursiveFunction();
}
-
종료 조건 (Base Case): 재귀 호출을 멈추기 위한 조건으로 종료 조건이 없으면 함수가 무한히 실행되서 스택 오버플로(Stack Overflow) 에러가 발생한다.
-
재귀 호출 (Recursive Case): 함수가 자기 자신을 호출해서 문제를 점점 작게 나눈다.
재귀함수는 for나 while 등의 반복문으로 대체 가능한데 왜 사용을 하는걸까?
자바스크립트 안에 있는 이 배열의 숫자 총합을 구해야한다고 가정하자.
이 배열에는 요소로 숫자가 있을 수도 있고 또 다른 배열이 있을 수도 있다.
이렇게 배열이 섞였을 경우에는 for문으로 한다면 겹으로 작성을 해줘야 한다.
배열안에 배열이 또 있을 수도 있고 그게 몇 단계로 내려갈지 알 수 없는 상황이라면 for문을 겹겹으로 사용해도 결과를 장담할 수가 없다.
물론 위치를 저장하는 등의 방식으로 다 처리할 수 있게 짤 수는 있겠지만 코드가 굉장히 길어지고 복잡해진다.
이럴 때 바로 재귀함수를 사용한다!
배열의 요소가 숫자면 그대로 더하고,
배열이라면 재귀로 똑같이 파고들도록 하면 훨씬 간결한 코드가 된다.
이처럼 재귀함수로 코드를 작성하면 보다 효율적으로 코드를 짤 수 있는 종류의 문제들이 있다.
방금 문제처럼 여러 단계를 포함할 수 있는 데이터를 다루는 문제나, 각종 정렬 알고리즘들도 있다.
재귀함수를 머릿속으로 돌리는 일이 입문자에게는 진입장볍이 될 수 있지만 재귀적 사고에 한 번
익숙해지고 나면 전보다 다양한 문제들을 수월히 풀 수 있게 될것이다.
단점
-
성능 문제: 호출 스택이 커지면 스택 오버플로(Stack Overflow)가 발생할 수 있다.
재귀 호출이 많아지면 성능 저하(메모리 사용 증가)가 있을 수 있다. -
무한 루프 위험: 종료 조건을 잘못 설정하면 함수가 무한히 호출된다.
이런 단점을 해결하기 위해서 많은 언어들에서 '꼬리 재귀 최적화'라는 기능을 제공한다.
재귀함수를 컴퓨터가 재해석해서 선형 알고리즘으로 만들어 실행하게 된다.
그럼 아무리 반복이 많이 일어나도 스택이 넘치는 일은 발생하지 않게 된다.
하노이의 탑..?
원리를 들어보면 굉장히 쉬워보이는데 주말에 한 번 풀어봐야겠다.
하노이의 탑에서 재귀가 쓰이는지 확실히 이해되지 않지만 재귀함수도 알아둬야겠지..ㅠ
