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

재귀용법(Recursive Call)은 함수가 자기 자신을 다시 호출하는 것을 의미한다. 재귀는 알고리즘을 설계 및 구현할 때 매우 유용한 방법 중 하나로, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 분할 정복(Divide and Conquer) 전략의 핵심 요소다.

장점

1. 코드가 더 간결하고 이해하기 쉽다.
2. 복잡한 문제를 간결하게 표현할 수 있다.

단점

1. 메모리 소비가 높을 수 있다.(스택 메모리 사용 증가)
2. 비재귀적인 방법보다 느릴 수 있다.
3. 기본단계에 도달할 때까지 함수가 계속 호출되므로, 잘못 구현하면 스택 오버플로우가 발생할 수 있다.

함수는 내부적으로 위와같이 스택처럼 관리된다.

재귀용법은 적절하게 사용 할 수 있으면 문제 해결을 쉽게 할 수 있어, 다양한 알고리즘에서 이용된다. 그러나 재귀의 복잡성과 메모리 사용에 대한 이해가 필요하다.

예제

팩토리얼을 구하는 알고리즘을 Recursive Call을 활용해서 알고리즘 작성하기

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

다음은 팩토리얼이 어떻게 계산되는지 보여준다.

factorial(3) = 3 * factorial(2)
             = 3 * (2 * factorial(1))
             = 3 * (2 * 1)
             = 6

재귀용법의 일반적인 형태

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

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

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

연습예제1. 팩토리얼

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

    
print(factorial(3)) # 6

연습예제2. 리스트의 합

"""
아래와 같은 리스트가 있을 때, 이 리스트 안의 숫자의 합을 구하는 함수를 만들기.
"""
import random 
data = random.sample(range(100), 10)
data # [72, 50, 8, 38, 77, 32, 90, 48, 74, 79]

data = [72, 50, 8, 38, 77, 32, 90, 48, 74, 79]


def list_sum(list_data):
    sum = 0
    for i in range(len(list_data)):
        sum = sum + list_data[i]
    print(sum)
    return sum


list_sum(data) # 568
"""
잘 풀었지만, 재귀를 사용하여 풀지는 못하였다.
"""

풀이

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

코드 분석

기저 조건 (Base case)

if len(string) <= 1:
    return True

만약 string의 길이가 1 이하라면 (즉, 문자열이 비어 있거나 한 글자만 있다면), 해당 문자열은 자동으로 회문으로 간주되어 True를 반환한다.

회문 판별

if string[0] == string[-1]:
    return palindrome(string[1:-1])
else:
    return False

• 문자열의 첫 번째 문자와 마지막 문자를 비교한다.
• 만약 두 문자가 같다면, 그 두 문자를 제외한 나머지 부분에 대해 다시 palindrome 함수를 호출한다. 이렇게 재귀 호출을 사용하여 문자열이 회문인지 판별한다.
• 만약 두 문자가 다르다면, 해당 문자열은 회문이 아니므로 False를 반환한다.

참고: 파이썬 리스트 슬라이싱

리스트의 서브셋(subset)또는 부분 리스트를 가져오는 매우 유용한 기능.

# 기본 구조는 아래와 같다.
list[start:end:step]
"""
start: 슬라이싱을 시작할 인덱스 (포함됨).
end: 슬라이싱을 끝낼 인덱스 (포함되지 않음).
step: 인덱스의 간격. 예를 들어, step이 2라면 한 항목을 건너 뛰어서 슬라이스된다.
"""

리스트 슬라이싱의 예제는 아래와 같다.

# 기본 슬라이싱
lst = [0, 1, 2, 3, 4, 5]
print(lst[1:4])  # 결과: [1, 2, 3]

# 시작과 끝 인덱스 생략
print(lst[:])    # 결과: [0, 1, 2, 3, 4, 5]
print(lst[2:])   # 결과: [2, 3, 4, 5]
print(lst[:3])   # 결과: [0, 1, 2]

# step사용
print(lst[::2])  # 결과: [0, 2, 4]

# 음수 인덱스를 사용하여 역순으로 슬라이싱
print(lst[::-1])  # 결과: [5, 4, 3, 2, 1, 0]

# 음수 인덱스 사용
print(lst[-4:-1])  # 결과: [2, 3, 4]

슬라이싱은 원본 리스트를 수정하지 않는다. 대신에 새로운 리스트를 반환한다.
슬라이싱은 인덱스 범위르 벗어나더라도 오류를 발생시키지 않는다. 가능한 최대 범위까지만 반환한다.

연습예제4. 리스트의 합

1, 정수 n에 대해
2. n이 홀수이면 3 X n + 1 을 하고
3. n이 짝수이면 n 을 2로 나눈다.
4. 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복한다.

오답코드

def calculate_loop(num):
    if num == 1 or 2:
        print(num)
        return num
    elif num % 2 == 0:
        new_num = num/2
        print(new_num)
        calculate_loop(new_num)
    elif num % 2 == 1:
        new_num = 3*num + 1
        print(new_num)
        calculate_loop(new_num)


a = calculate_loop(200)
print(a)

이 조건문은 "num이 1인가?" 또는 "2는 참인가?" 라는 두 개의 질문을 하는 것으로 해석된다. 파이썬에서 0이 아닌 모든 숫자는 불리언(Boolean) 컨텍스트에서 True로 간주되므로 2는 항상 True이다. 따라서 이 조건문은 항상 참이 된다.

우리는 num이 1 또는 2인 경우를 체크해야 하므로, 코드를 다음과 같이 수정해야 한다.

def calculate_loop(num):
    if num == 1 or num == 2:
        print(num)
        return num
    elif num % 2 == 0:
        new_num = num/2
        print(new_num)
        calculate_loop(new_num)
    elif num % 2 == 1:
        new_num = 3*num + 1
        print(new_num)
        calculate_loop(new_num)

a = calculate_loop(200)
print(a)

하지만, 'print(a)'에서 'None'이 출력되는 것을 볼 수 있다. 그 이유는, 'calculate_loop'함수에서 몇몇 경로에서 값을 반환하지 않기 때문이다.

구체적으로, calculate_loop 함수는 num이 1 또는 2일 경우 값을 반환한다. 그러나 num이 그 외의 값일 경우 재귀적으로 calculate_loop 함수를 호출하지만, 이 재귀 호출의 결과를 반환하지 않는다.

따라서, 최종적으로 a에 할당되는 값은 None이 된다.

이 문제를 해결하기 위해서는 재귀 호출의 결과를 반환하도록 코드를 수정해야 한다.

정답 코드

def calculate_loop(num):
    if num == 1 or num == 2:
        print(num)
        return num
    elif num % 2 == 0:
        new_num = num/2
        print(new_num)
        return calculate_loop(new_num)
    elif num % 2 == 1:
        new_num = 3*num + 1
        print(new_num)
        return calculate_loop(new_num)

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

연습문제5

문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 2+1+1
5. 2+2
6. 1+3
7. 3+1

정수 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)

func(5) # 13