재귀 함수

재귀 (recursion)

-함수가 수행 도중 자기 자신을 다시 호출하는 기법

-대부분의 재귀는 반복으로 바꾸어 작성 가능

재귀함수의 조건

-자기 자신을 다시 호출하는 부분이 존재해야함 (인자를 다르게 넣어서)

-재귀를 끝낼 조건이 필요함 (종료 조건이 없으면 오류 발생 시 까지 무한 호출)

+ void 함수가 아니라면 각 조건에 return이 필요한 듯

 재귀함수의 특징

-구현이 쉽다. (...? 사실 이해가 잘 안간다ㅠ)

-코드 이해가 직관적으로 쉬워진다. 

-코드가 간결해진다.

-일반적으로 시간적, 공간적으로 오버헤드가 크다. 

-효율이 떨어진다. (오버헤드가 커서)

 

재귀함수가 효율적인 문제

-거듭제곱 문제

O(log_2⁡n) 

 

예시) 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), 반복이 더 효율적이다.