재귀 (Recursion)

재귀함수

- 자신을 정의할 때 자기 자신을 재참조하는 함수

 

ex)

def factorial(n)

    if n ==1 :

         return 1

    return n * factorial(n-1)

 

구성요소 2가지

-recurrence relation (점화식)

ex) 위에 factorial함수는 점화식으로 표현하면 f(n) = n*f(n-1)

-base case(더이상 재귀호출을 하지 않아도 계산값을 반환할 수 있는 조건을 말한다. basecase가 있어야 재귀함수의 무한루프를 방지할 수 있다)

 

시간 복잡도

- 재귀함수 전체 시간복잡도 = 재귀 함수 호출 수 * (재귀 함수 하나당) 시간복잡도