순환(Recursion)
재귀호출(순환호출)
•
자기 자신을 호출해서 순환 수행되는 것
◦
알고리즘이나 함수가 수행 도중에 자기 자신을 반복 호출하여 문제를 해결하는 기법
◦
Induction(수학적 귀납법)
•
전체 문제를 한 번에 해결하기보단,
같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적인 경우에 사용
Recursion이란
하위 작업
현재 수행 중인 작업의 하위 단계(좀 더 작은 단위 작업)
베이스 케이스(base case)
재귀호출하는 과정을 반복하다가, 한번에 해결할 수 있을 정도로 분할된 작업 단위가 충분히 작아지는 단계
더 이상 자신을 호출하지 않고도 문제가 해결되는 단계
팩토리얼 프로그래밍
반복적 방식(Iteration) vs 순환적 방식(Recursion)
•
메모리 공간(Iteration 승)
◦
Recusrion이 더 메모리를 잡아먹는다
▪
함수를 여러번 호출함으로써, 메모리 할당이 많음
•
구현 용이성(Recursion 승)
◦
매우 복잡한 코드(매우 어려운 문제)를 구현해야할때, 순환적 방식이 더 구현하기가 용이하다
대부분의 순환(Recursion)은 반복(Iteration)으로 바꿔서 작성 가능
웬만하면, 반복(Iteration)방식으로 구현을 해야한다
그렇다면, 무조건 반복적 방식이 수행 속도가 무조건 빠를까?
답은, 아니다
거듭제곱 값을 구하는 함수인 경우를 살펴보겠습니다
거듭제곱 값을 구하는 문제는 결론부터 말하자면,
순환적 방법이 더 효율적인 문제입니다.
반복적 함수
•
시간 복잡도
◦
O(N)
•
실제 수행 속도
◦
7.17초
순환적 함수
•
시간 복잡도
◦
O(logN)
•
실제 수행 속도
◦
0.47초
