알고리즘 공부 4일차

재귀함수

자신을 정의할 때 자기 자신을 재참조하는 함수를 뜻한다.

def factorial(n):
	if n == 1:
    	return 1
    return n * factorial(n-1)

def fibo(n):
	if n == 1 or 2:
    	return 1
    return fibo(n-1) + fibo(n-2)

구성요소 2 가지가 필요하다
1. recurrence relation 점화식
관계식으로 표현하는것 ex) f(n) = n * f(n-1)
2. base case
더이상 재귀호출을 하지 않아도 계산값을 반환할 수 있는 상황(조건)을 말합니다.

시간 복잡도

재귀함수 전체 시간복잡도 = 재귀 함수호출 수 X (재귀 함수 하나당) 시간 복잡도
| Execution Tree(recursion tree) : 재귀 함수의 실행 흐름을 나타내는데 사용되는 트리

트리 (Tree)

서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어 있습니다.