기타 기본 지식
재귀 함수
yehey
2020. 10. 20. 00:12
재귀 (recursion)
-함수가 수행 도중 자기 자신을 다시 호출하는 기법
-대부분의 재귀는 반복으로 바꾸어 작성 가능
재귀함수의 조건
-자기 자신을 다시 호출하는 부분이 존재해야함 (인자를 다르게 넣어서)
-재귀를 끝낼 조건이 필요함 (종료 조건이 없으면 오류 발생 시 까지 무한 호출)
+ void 함수가 아니라면 각 조건에 return이 필요한 듯
재귀함수의 특징
-구현이 쉽다. (...? 사실 이해가 잘 안간다ㅠ)
-코드 이해가 직관적으로 쉬워진다.
-코드가 간결해진다.
-일반적으로 시간적, 공간적으로 오버헤드가 크다.
-효율이 떨어진다. (오버헤드가 커서)
재귀함수가 효율적인 문제
-거듭제곱 문제
O(log_2n)
예시) power(2,10)
power(2,10) -> power(4,5) -> 4*power(16,2) -> 4*power(256,1) -> 4*256*power(256^2,0) -> 4*256*1 = 1024
재귀가 비효율적인 문제
-피보나치 수열
O(2^n)
피보나치수열을 반복 구현하면 O(n), 반복이 더 효율적이다.