Recursive ( 재귀 )

https://www.fun-coding.org/Chapter14-dp_divide.html

파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩

https://www.fun-coding.org/Chapter13-recursive.html

파이썬과 컴퓨터 사이언스(기본 알고리즘): 재귀 용법 (Recursive Call) - 잔재미코딩

---

■ 재귀

1) 정의 :

> 함수 안에서 동일한 함수를 호출하는 형태로 문제를 해결

   ( 제일 작은 단위까지 내려가서 divide and conquer )

- 파이썬 기준

→ sys.setrecursionlimit( N ) 으로 재귀 깊이 설정 가능

 

> 재귀 함수의 구현 방식 2가지

# 일반적인 형태1
def function(입력):
    # 입력이 일정 값 이상이면
    if 입력 > 일정값:  
        return function(입력 - 1)  # 입력보다 작은 값
    else:
        return 일정값 # 재귀 호출 종료

# 일반적인 형태2
def function(입력):
    # 입력이 일정 값보다 작으면
    if 입력 <= 일정값:              
        return 결과값   # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값

 

> 재귀함수와 stack

- 함수가 계속 불리면서 마지막 fuction call이 아닌 return을 만나면 스택이 빠지면서 return들을 반환해주고

계산 이후 결과를 return 해줌

---

 

2) 예시 :

# 반드시 return을 붙여주어야 stack에서 결과를 받으면서 하위 스택으로
# 결과를 넘겨줄 수 있음
        

def factorial(num):
    print(f'num : {num}')
    if num > 1:

        return num * factorial(num - 1)
    else:
        return num

print(factorial(6))

>>> 
num : 6
num : 5
num : 4
num : 3
num : 2
num : 1
720

def factorial_2(num):
    print(f'num : {num}')
    if num <= 1:
        return num
    else:
        return num * factorial(num - 1)

print(factorial(6))
>>>
num : 6
num : 5
num : 4
num : 3
num : 2
num : 1
720

 

3) 시간 복잡도

- O(n)

  마지막 1번 호출 제외, stack 형식으로 n-1의 recursive 함수 호출

  ( === n-1 반복문을 호출한 것과 동일 )