📌 재귀 용법(recursive call, 재귀 호출)

• 재귀 용법 : 함수 안에서 동일한 함수를 호출하는 형태
• 엄밀히 따지자면 재귀 용법 자체가 알고리즘은 아니지만, 이후 고급 알고리즘을 다룰 때 사용되므로 익혀놓도록 하자~

---

📌 재귀 호출의 일반적 형태

💡 형태 1

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

💡 형태 2 (형태 1에서 순서만 살짝 바꿈)

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

---

📌 재귀 호출 예제로 이해하기

$n!:1×2×...×n$ : 재귀 호출을 이용하여 팩토리얼 함수 구현하기

✅ 형태 1번으로 구현하기

def factorial(num):
    if num > 1:
        return num * factorial(num - 1)
    else:
        return num

✅ 형태 2번으로 구현하기

def factorial(num):
    if num <= 1:
        return num
    return_value = num * factorial(num - 1)
    return return_value

---

📌 재귀 호출과 스택

• 재귀 호출은 스택(stack: LIFO 방식의 자료구조)의 전형적인 예이다.
• 재귀 함수은 내부적으로 스택처럼 관리 된다.

---

📌 재귀 용법의 다양한 활용

1) 1부터 num까지의 곱을 출력하는 재귀 함수

def multiple(num):
    if num <= 1:
        return num
    return num * multiple(num - 1)

2) 숫자가 들어있는 리스트의 합을 리턴하는 재귀 함수

data = [1, 3, 5, 2, 6, 7]

def sum_list(data):
    if len(data) <= 1:
        return data[0]
    return data[0] + sum_list(data[1:])

3) 회문(palindrome)을 판별할 수 있는 함수

회문(palindrome: 순서를 거꾸로 읽은 것과 제대로 읽은 것의 결과가 같은 단어나 문장)

def palindrome(string):
    if len(string) <= 1:
        return True
    
    if string[0] == string[-1]:
        return palindrome(string[1:-1])
    else:
        return False

4) 1, 2, 3의 조합만으로 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수

f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾아내기!

def func(data):
    if data == 1:
        return 1
    elif data == 2:
        return 2
    elif data == 3:
        return 4
   
    return func(data -1) + func(data - 2) + func(data - 3)