재귀함수

재귀함수?

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

예시

1. 팩토리얼 구현

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

2. 피보나치 수열 구현

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

💡 피보나치 수열??
https://m.blog.naver.com/prayer2k/222432519342

토끼의 번식에 관한 문제에서 시작되었다. 처음에 한쌍의 토끼가 있고 두 달이 지나면 번식이 가능하다고 해보자. 또한 이 토끼들을 죽지 않는다고 하였을 때 처음엔 한쌍, 두달이 지나면 두 쌍 다시 두달이 지나면 세쌍(처음 한쌍이 2달이 지나서 또 번식) 이런식으로 늘어날 것이다. 결국, 1, 1, 2, 3, 5, 8, 13, . . . 과 같은 수열이다. 이런 수열을 정사각형으로 그려서 붙이면 나선형이 되는데 이것을 황금비라고 한다

구성요소 2가지

점화식(recurrence relation)

$fn$을 $f(n—1), f(n-2), … , f(2), f(1)$의 관계식으로 표현하는 것을 recurrence relation 이라고 한다.

예시

1.Factorial

f(n) = n *f(n-1)

 

2. Fibonacci sequence

f(n) = f(n - 1) + f(n -2) 

 

3. Pascal’s Triangle

f(n , m) = f(n-1,m-1) + f(n-1, m)

 

점확식을 알고있다면 그대로 코드로 옮기면 된다 단, 조건을 꼭 적어주자 안그러면 무한으로 즐겨진다

base case

바로 그 조건을 적어주는 것이 base case이다

• 더 이상 재귀호출을 하지 않아도 계산값을 반환할 수 있는 상황
• 모든 입력이 최종적으로 base case를 이용해서 문제를 해결할 수 있어야 한다.
• base case가 무조건 있어야 재귀함수의 무한 루프를 방지할 수 있다.

시간 복잡도

💡 재귀함수 전체 시작복잡도 = 재귀함수 호출 수 X (재귀함수 하나당) 시간 복잡도

O(n) n에 비례한 호출

f(n) = n *f(n-1)

O(2^n) 2^n에 비례한 호출

f(n) = f(n - 1) + f(n -2)

O(log2n)

• Binary search