재귀함수 Recursion

재귀함수 Recursive Function

자기 자신을 호출하는 함수

I went through it in Angela's module.

팩토리얼 Factorial 예시

0! = 1
1! =1 
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6 

재귀적으로 문제를 푼다 =
같은 형태의 더 작은 문제를 먼저 풀고
(부분문제 = subproblem) 부분 문제의 답을 이용해서 기존 문제를 푼다.

재귀 함수를 풀 때는 경우를 나눠주어야한다

n!
n=0인 경우 n!=1        -> base case
n>0인 경우 n!=(n-1)!xn -> recursive case

• Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

• Recursive case: 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우

베이스 케이스가 없으면 재귀 함수가 계혹해서 호출하면서 끝나지 않음

02. 재귀 활용 예시 4:08

e.g.1 재귀함수로 피보나치 수열 나타내기

# n번째 피보나치 수를 리턴
def fib(n):
    if n <= 2:  (or n < 3)
        return 1
    return fib(n-2) + fib(n-1)    

# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

• 베이스 케이스: 피보나치 수열의 정의 자체가 첫 번째 항과 두 번째 항이 111이고 세 번째 항부터는 앞선 두 항의 합인 수열입니다. 그렇기 때문에 n이 1이거나 2면 고민할 것도 없이 리턴값은 1이 되겠죠.

• recursive case: “같은 형태의 더 작은 부분 문제"
  n이 5면, fib(4) 와 fib(3)을 더해주면 되는데, 이것을 일반화하면 fib(n - 1)과 fib(n - 2)를 더하는 것입니다.

피보나치 수열 재귀함수의 시간 복잡도

재귀함수와 숫자합

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    if n == 1:
        return 1
    return triangle_number(n-1) + n    

# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))

숫자 합의 시간복잡도

시간 복잡도

일단 재귀적인 호출을 제외하고 시간 복잡도를 생각해 봅시다. Base case의 시간 복잡도는 인풋 크기와 연관이 없으니까 O(1)입니다. Recursive case에서는 triangle_number(n - 1)의 재귀적 호출을 제외하면 O(1)입니다.

그런데 재귀문을 통해서 triangle_number 함수는 총 n번 호출되니까, 총 O(n)의 시간이 걸리게 되죠.

반복문 = 재귀 함수

• 재귀함수의 단점: 함수가 다시 어디로 돌아와야 할지 기록해두는 공간 Call Stack(기록하는 공간), 한계점에 도달할 때 과부하 Stack overflow. 파이썬은1000개 까지만 허용. 그 이상
  recursion error

따라서 상황에 따라 반복문, 재귀함수를 쓰는 게 더 깔끔하고 효율적이겠다라고 판단하고 사용해야함. call stack이 너무 많이 쌓일 것같다면 반복문을 쓰는게나음