재귀

재귀함수란?

재귀 함수(Recursive function)는 함수가 자기 자신을 호출하는 것을 의미

재귀적인 호출은 종종 복잡한 문제를 해결할 때 유용함

예를 들어, 트리 구조를 탐색하거나, 팩토리얼 계산, 피보나치 수열 등의 알고리즘에서 많이 사용

재귀 함수는 종료 조건과 재귀 호출의 두 부분으로 구성

종료 조건은

재귀 호출이 중단되어야 하는 시점을 정의

종료 조건 없이 재귀 함수를 작성하면 무한 루프에 빠질 수 있으므로 주의가 필요

재귀 호출은

반복문과 같은 반복적인 로직으로 변환하여 코드를 작성하는 것이 중요

또한, 재귀 함수는 호출할 때마다 함수의 인자를 스택 메모리에 저장하므로,

스택 메모리를 과도하게 사용할 가능성이 있음

따라서 재귀 함수를 작성할 때는 스택 메모리 사용량을 최소화하는 것이 중요

재귀함수의 장점

• 불필요하게 여러 개의 반복문을 사용하지 않기 때문에, 코드가 간결해지고, 수정이 용이
• 변수를 여러 개 사용할 필요가 없음

**재귀 함수의 단점**

• 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어려움

• 반복하여 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장

  이러한 과정은 반복문에 비해서 메모리를 더 많이 사용하게 되어 많은 메모리를 사용

• 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 됨

**재귀 함수를 사용하기 위한 조건**

• 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 함
• 재귀 호출이 종료되는 시점이 존재해야 함

**재귀적 사고**

**1. 재귀 함수의 입력값과 출력값 정의하기**

**2. 문제를 쪼개고 경우의 수를 나누기**

**3. 단순한 문제 해결하기**

**4. 복잡한 문제 해결하기**