재귀1 재귀 함수 이론 정리와 피보나치 수열 재귀함수 : 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법이다. 따라서 순환적으로 정의된 문제나 알고리즘을 풀기 적합하다. 예를들어 팩토리얼, 피보나치수열, 이항계수, 이진트리, 이진탐색, 하노이탑 문제를 풀기 적절하다. 재귀함수는 호출부분과 멈추는 부분으로 나뉘어진다. 멈추는 부분이 없으면 무한히 호출하게 된다. 장점: 알고리즘을 명확하고 간결하게 쓸 수 있다. 단점: 함수호출을 여러번 하므로 메모리와 속도면에서 성능이 떨어진다. 반복문보다 재귀가 더 빠른 경우가 있다. 재귀함수는 재귀호출을 할 때마다 더 작은 문제로 쪼개지는데, 선형적으로 작아진다면 시간복잡도는 O(n)으로 반복문과 동일하다. 문제를 반으로 쪼개서 해결하는 경우 시간복잡도는 O(logn)으로 효율적이다. Head Re.. 2020. 9. 6. 이전 1 다음
