재귀함수(Recursive Function)

정의 : 함수 안에 자신의 함수를 다시 호출하는 함수를 의미한다. 이러한 재귀함수는 로직을 내부적으로 반복하다가

          일정한 조건이 만족되면 함수를 이탈하여 결과를 출한다.

 

이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)이다.

 

다음 예시 그림을 보자

Factorial

 

인자를 5를 넣으면 5 * 4 * 3 * 2 * 1이 되는 것이다.

 

 

함수를 호출할 때마다 콜스택에는 함수의 매개변수, 지역변수, 반환주소 값 등을 모두 저장하게 되는데, factorial(5)를

호출하게되면 반환타입 부분에서 5 * factorial(5-1)이 수행되면서 factorial(4)가 호출되고 반환을 기다리게 된다.

→ 이 방식을 반복

 

문제점

이러한 재귀 함수 사용에는 스택 오버플로우(stack overflow)를 주의해야한다.

 

장점

- 변수를 여럿 만들 필요가 없다.

  예를 들어 현재 상태를 저장해야 할 경우 tmp변수를 만들기보다 메서드를 재귀적으로 호출하면서 변경된 상태를

  전달함으로써 변수의 수를 줄일 수 있다.

- while문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해진다.

 

단점

- 지속적으로 함수를 호출하게 되면서 모든 값ㅇ르 process stack에 저장해야한다. 이런 과정은

  선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 된다.

- 함수 호출이 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 한다.