재귀 (Recursion)

재귀 - 함수를 정의할때 자기 자신을 재참조. 그래프 탐색, 트리,  DP 등 다양한 알고리즘에 사용됨.

• Factorial 

def factorial_ex(n)
	if n == 1:
    	print("factorial ex")
        return 1
    return n * factorial_ex(n-1)
    
# 시간복잡도 O(n)

• Fibonacci

def fibonacci_ex(n)
	if n  == 1 or n == 2:
    	print("fibonacci ex")
        return 1
    return fibonacci_ex( n -1 ) + fibonacci_ex(n - 2)

#시간복잡도 O(2^n)

 

점화식(recurrence relation) : f(n) = f(n-1)+ f(n-2). 자기 자신을 참조하는 개념

 

무한 루프에 빠지지 않도록 base case(더 이상 자기 자신을 재참조 하지 않음)를 설정해 주어야함.