[알고리즘] #2 재귀 용법

** 재귀 용법(Recursive Call, 재귀 호출)

• 함수 안에서 동일한 함수를 호출하는 형태

 

 

** 예제

• 팩토리얼을 구하는 알고리즘
• 분석: 규칙이 보임 n! = n * (n-1)!

---

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

---

 

 

** 예제: 시간 복잡도와 공간 복잡도

• factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함
• 일종의 n-1번 반복문을 호출한 것과 동일
• factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨
• 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)

 

 

** 재귀 호출의 일반적인 형태

---

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

 

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

 

# 일반적인 형태2: 팩토리얼

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

---

   

 

** 재귀 호출은 스택의 전형적인 예

• 함수는 내부적으로 스택처럼 관리됨
• 파이썬에서 재귀 함수는 깊이가 1000회 이하가 되어야 한다는 제약 사항이 있음

 

Live Programming Mode - Python Tutor - Visualize Python and JavaScript code

 

 

 

 

** 재귀 용법 활용

1) 1 부터 num 까지의 곱

• 패턴: 곱 = num * 곱(num-1)

---

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

---

 

2) 리스트의 합

• 패턴: 합 = 첫번째 원소 + 합(첫번째 이후 원소)

---

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) 정수 n에 대해, n이 홀수이면 3 * n + 1, n이 짝수이면 n을 2로 나눈다. n이 1이 될 때까지 반복하는 과정을 출력

---

def func(n):
    print (n)
    if n == 1:
        return
    
    if n % 2 != 0: # 홀수
        return (func((3 * n) + 1))
    else: # 짝수
        return (func(int(n / 2)))

---

 

5) 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수

• 패턴: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수 f(n) = f(n-1) + f(n-2) + f(n-3)

 

 

---

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

---