[알고리즘] 재귀 Recursion

재귀(Recursion)

• 어떠한 것을 정의할 때 자기 자신을 참조하는 것
• 재귀적 정의 또는 순환 정의 라고도 함

 

재귀 함수(Recursive Function) / 재귀 알고리즘(Recusive Algorithm)

• 하나의 함수에서 자기 자신을 다시 호출해 수행하는 알고리즘
• 귀납적 문제 해결 방식(기존의 절차지향적인 문제 해결 방식과는 다름)
• 모든 재귀 함수는 반복문으로 치환 가능
  • 상황에 따라서 반복문이 코드가 너무 길고 복잡해질 경우 재귀 함수 사용
  • 반복문 대신 재귀 함수로 구현했을 경우 코드가 간결하지만, 메모리/시간 측면에서 손해
• 자기 자신을 여러 번 호출하는 것은 비효율적!
• 재귀 호출 시에는 스택 영역에 계속 누적됨

 

접근방식

1. 함수의 정의
2. Base Condition 정의(필수)
   • 자기 자신을 호출하지 않고 재귀 함수를 빠져나올 수 있는 조건
3. 재귀식 정의

 

---

출처 : Youtube, BaaarkingDog