CS/자료구조
[자료구조] 순환 - Recursion
02 순환 Recursion 1. 순환의 개념 1-1. 순환이란? 순환이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법이다. 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법이다. 순환의 가장 간단한 예로는 팩토리얼있다. 아래는 c언어로 팩토리얼 구하는 함수를 만든 것이다. int factorial(int n){ if (n ... -> 21 -> 20) 즉, 호출을 할 때마다 문제의 크기가 2로 나눈 것만큼 줄어들기 때문에 시간복잡도가 O(log2 n)이다. 반면 반복문은 n만큼 반복 연산해야하기 때문에 시간복잡도가 O(n)이다. 물론 수학적인 방식을 이용했기때문에 당연히 순환적인 방식이 빠를 수밖에 없는 거 아닌가라고 생각할 수 있을 것이다. 그러나 반복문에서는 ..
