알고리즘 기초 - 재귀 호출(Recursive Call)

🌈 재귀 호출(Recursive Call)

🔥 재귀 호출이란?

🔥 재귀 호출과 반복문 비교

🔥 재귀 호출 예시

1. 재귀 호출이란?

1) 재귀 함수 개념

• 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미함
  
• 재귀 함수 단순 예제
• 어느 정도 출력하다 최대 재귀 깊이 초과 오류가 발생하는데, 이는 python에서 메모리 제한을 두었기 때문
  👉🏻 RecursionError: maximum recursion depth exceeded while calling a Python object

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function()

2) 재귀 함수 특징

• 스택처럼 호출한 함수를 쌓았다가 종료조건을 만나면 위에서부터 하나씩 꺼래 처리하는 방식임

# 100번째 호출 했을 때 종료되는 조건을 가진 재귀 함수
def recursive_function(i):
    if i == 100:
        return
    print(f'{i}번째 재귀함수에서, {i+1}번째 재귀함수를 호출합니다.')
    recursive_function(i + 1)
    print(f'{i}번째 재귀함수를 종료합니다.')
recursive_function(1)

3) 재귀 일반적 형태

• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출되기 때문에 재귀 함수를 사용할 때는 재귀 함수의 종료 조건(제한)을 반드시 명시함

# 재귀 함수 일반적인 형태1
def function(입력값):
    if 입력값 > 제한값:
        return function(입력값-1)
    else:
        return 제한값 또는 특정값 # 👈 재귀 호출 종료

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

2. 재귀 호출 반복문 비교

• 재귀 호출은 점화식과 종료조건만 구현하면 만들 수 있기 때문에 가시성이 높고, 구현하기 쉽다는 장점이 있음
• 단, 1000번(약 997번) 정도까지만 재귀호출이 가능하기 때문에 많은 호출이 필요할 때에는 사용 불가
• 또한 재귀호출과 반복문 구현은 시간 복잡도는 같으나, 실제 Call Stack에 과정에서 재귀호출이 속도가 느리고, 메모리를 크게 차지함
• 즉, 반복문 구현은 전체 과정을 서술해야하기 때문에 재귀호출 보다 구현이 복잡하나 속도가 빠르고 호출의 제한이 없다는 장점이 있음

1) 피보나치 수열 구현

# 재귀 함수 구현
import time
def fibonacci(n):
    if n == 1:
        return 1
    return fibonacci(n-1) + n
start = time.time_ns()
print(fibonacci(100)) # 5050
print('time :', time.time_ns()-start) # 83000
# print(fibonacci(1000)) # 오류 발생

# 반복적 구현
import time
def fibonacci(n):
    res = 1
    for i in range(2, n+1):
        res += i
    return res
start = time.time_ns()    
print(fibonacci(100)) # 5050
print('time :', time.time_ns()-start) # 11000

# 구현 최적화(수학적 구현:가우스의 덧셈)
import time
def fibonacci(n):
    return n * (n + 1) // 2
start = time.time_ns()    
print(fibonacci(100)) # 5050
print('time :', time.time_ns()-start) # 3000

3. 재귀 호출 예시

1) 팩토리얼(factorial)

• factorial : n! = 1 x 2 x 3 ...... (n-1) x n
  🔥 수학적으로 0!(factorial 0) 1!(factorial 1)은 모두 1임
• 시간 복잡도는 O(n-1)이기 때문에 O(n)과 같음

# 반복문으로 구현한 factorial
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
        result = result * i
    return result
print(f'반복문으로 구현 : {factorial_iterative(5)}') # 120    

# 재귀 호출로 구현한 factorial
def factorial_recursive(n):
    if n <= 1: # n이 1이하인 경우 1를 반환
        return 1
    # n! = n * (n-1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n-1)
# 출력 : n이 5일 때
print(f'재귀 호출로 구현 : {factorial_recursive(5)}') # 120

2) 최대공약수(유클리드 호제법)

• 유클리드 호제법이란 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘임
• 두 자연수 A,B에 대하여 A를 B로 나눈 나머지를 R이라고 가정(A>B)
• 이 경우, A와 B의 최대공약수는 B와 R의 최대공약수와 같음

def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)
print(gcd(192,162)) # 6

3) n이 주어졌을 때, 1부터 n까지 곱하는 재귀함수

• for문으로 구현했을 때는 변수(retrun_value)에 중첩하여 곱하는 방법으로 구현 가능
• 재귀함수로 구현했을 때는 1일 때는 1을 return해주고, 1이 아닐 때는 num*재귀함수(num-1)로 처리

# for문으로 구현
def multiple(num):
    return_value = 1
    for i in range(1, num+1):
        return_value = return_value * i
    return return_value
print(multiple(5))

# 재귀 함수로 구현
def multiple(num):
    if num <= 1:
        return num
    return num * multiple(num-1) 
print(multiple(10))

4) 리스트의 합을 구하는 재귀함수

• 배열의 길이가 1 이하일 때는 맨 첫 값을 반환하고, 1보다 클 때는 배열의 첫번째 값에 배열의 길이를 2번째부터 끝까지 슬라이싱한 데이터를 재귀함수에 전달함
• 5의 길이를 가진 배열을 전달했을 때, data[-1] + data[-2] + data[-3] + data[-4] + data[-5] 가 최종 더해지기 때문에 모두 합한 것과 같음
• 재귀함수가 리스트나, 문자열을 통해 해결해야할 경우, 일반적으로 재귀 호출의 제한을 데이터의 길이로 정하고, 재귀 함수에 파라미터는 슬라이싱 기법을 통해 전달함

import random
def sum_list(data):
    if len(data) <= 1:
        return data[0]
    return data[0] + sum_list(data[1:])
data = random.sample(range(100), 10)
print(sum_list(data))

• pop을 통해 list의 합을 구현할 때는, 종료 조건으로 배열의 합을 반환시켜줌
• 함수의 파라미터로 배열과 배열의 합(res)의 초기 세팅인 0을 전달함
• 함수 내에서 pop을 통해 맨 뒤에 요소를 꺼내서 배열의 합(res)에 계속 더함

import random
def sum_list(arr, res):
    if len(arr) == 0: return res
    last = arr.pop()
    return sum_list(arr, res+last)
data = random.sample(range(100), 10)
print(sum(data))
print(sum_list(data, 0))

5) 단어를 입력 받아 회문(palindrome)인지 판단하는 함수

• 회문은 반대로 읽어도 그대로 읽어도 같은 구문을 의미함

def palindrome(word):
    if len(word) <= 1: # 👈 단어가 홀수이면 길이가 1일 때 회문, 짝수면 0
        return True
    if word[0] == word[-1]:
        return palindrome(word[1:-1])
    else:
        return False
print(palindrome('level')) # True

6) n이 홀수면 3 X n + 1을 하고, n이 짝수면 n을 2로 나눠 1이 될때가지 반복하는 재귀함수

def func(n):
    print(n)
    if n == 1:
        return n
    if n % 2 == 1:
        return func((3*n)+1)
    else:
        return func(n/2)
func(3)

7) 정수 n이 주어졌을 때, n을 1,2,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)
print(func(4)) # 7
print(func(5)) # 13
print(func(6)) # 24