재귀함수

재귀는 원래의 자리로 돌아오는 것을 뜻한다. 즉 재귀함수란 자기 자신을 리턴하는 함수를 말한다.

재귀 함수의 규칙

1. 함수는 실행시에 자기 자신을 반드시 리턴해야한다.
2. 종료되는 시점을 반드시 명시해줘야한다. 종료시점이 명시되지 않는다면 무한으로 재귀호출이 실행된다.

stack

재귀함수를 이해하기 위해서 스택의 개념을 이해하고 있으면 더 쉽다.
stack은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이다.

스택의 경우 입구가 하나이기 때문에 2이라는 자료를 꺼내기 위해서는 3을 먼저 꺼내고 2를 꺼내야하는 구조이다.

예시

대표적인 재귀함수의 예시로 팩토리얼이있다.

function factorial(n){
    if (n === 0) // 종료시점 명시
        return 1   
    return n * factorial(n - 1) // 자기 자신 호출
}

factorial(3)

n(3)부터 역순으로 1씩 감소하면서 재귀호출을 하고 n이 0이 되었을 때 재귀호출이 중단된다. 재귀호출에 대한 데이터가 아래와 같이 스택에 쌓이고 최종적으로 3x2x1x1 = 6의 값이 리턴되게 된다.