순환(Recursion)

재귀호출(순환호출)

• 자기 자신을 호출해서 순환 수행되는 것
  • 알고리즘이나 함수가 수행 도중에 자기 자신을 반복 호출하여 문제를 해결하는 기법
  • Induction(수학적 귀납법)
• 전체 문제를 한 번에 해결하기보단, 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적인 경우에 사용

Recursion이란

하위 작업

현재 수행 중인 작업의 하위 단계(좀 더 작은 단위 작업)

베이스 케이스(base case)

재귀호출하는 과정을 반복하다가, 한번에 해결할 수 있을 정도로 분할된 작업 단위가 충분히 작아지는 단계

더 이상 자신을 호출하지 않고도 문제가 해결되는 단계

팩토리얼 프로그래밍

반복적 방식(Iteration) vs 순환적 방식(Recursion)

• 메모리 공간(Iteration 승)
  • Recusrion이 더 메모리를 잡아먹는다
    • 함수를 여러번 호출함으로써, 메모리 할당이 많음
• 구현 용이성(Recursion 승)
  • 매우 복잡한 코드(매우 어려운 문제)를 구현해야할때, 순환적 방식이 더 구현하기가 용이하다