파이썬 재귀 함수의 사용 방법

재귀 함수란?

재귀 함수는 한 함수가 자기 자신을 호출하는 것을 말합니다. 파이썬에서는 함수가 자기 자신을 호출할 수 있는데, 이러한 기법을 재귀라고 합니다. 이러한 기법은 프로그래밍 문제를 해결하는데 매우 유용합니다.

재귀 함수를 사용하는 이유

대부분의 프로그래밍 문제는 재귀 없이 해결할 수 있습니다. 엄격히 말하자면, 재귀는 반드시 필요한 것은 아닙니다.

하지만 일부 상황에서는 재귀가 특히 유용합니다. 재귀를 사용하면 일련의 작업을 보다 간결하고 자연스러운 방식으로 표현할 수 있습니다. 예를 들어, 다음과 같은 문제를 생각해보겠습니다.

주어진 수를 1까지 1씩 감소시키면서 출력하는 프로그램을 작성하시오.

이러한 문제는 반복문을 사용하여 해결할 수 있습니다. 하지만 재귀 함수를 사용하면 더 간단하게 해결할 수 있습니다. 이제부터 차근차근 진행해보겠습니다.

Recursive Function Python - Step by Step

1. 먼저, 재귀 함수를 정의해야 합니다. 다음은 주어진 수를 출력하는 재귀 함수의 예입니다.

def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)

2. 이제 재귀 함수를 호출해보겠습니다. 다음은 5부터 1까지 출력하는 예입니다.

countdown(5)

실행 결과는 다음과 같습니다.

5
4
3
2
1

이와 같은 방식으로 재귀 함수를 사용하여 문제를 해결할 수 있습니다.

팩토리얼 계산하기

이제 재귀 함수를 사용하여 팩토리얼을 계산하는 문제를 해결해보겠습니다. 팩토리얼은 주어진 수에 대해 1부터 해당 수까지의 모든 수를 곱하는 것을 말합니다.

Python 팩토리얼 함수 정의하기

먼저, 재귀 함수를 사용하여 팩토리얼을 계산하는 함수를 정의해야 합니다. 다음은 주어진 수의 팩토리얼을 계산하는 재귀 함수의 예입니다.

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

팩토리얼 구현 방법 비교하기

다음으로, 재귀 함수를 사용하여 팩토리얼을 계산하는 방법과 반복문을 사용하여 팩토리얼을 계산하는 방법을 비교해보겠습니다.

import time

def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 재귀 함수를 사용한 팩토리얼 계산
start_time = time.time()
factorial_recursive(10)
end_time = time.time()
elapsed_time = end_time - start_time
print("재귀 함수 실행 시간:", elapsed_time)

# 반복문을 사용한 팩토리얼 계산
start_time = time.time()
factorial_iterative(10)
end_time = time.time()
elapsed_time = end_time - start_time
print("반복문 실행 시간:", elapsed_time)

실행 결과는 다음과 같습니다.

재귀 함수 실행 시간: 2.1457672119140625e-06
반복문 실행 시간: 1.1920928955078125e-06

위의 결과를 보면, 반복문을 사용한 팩토리얼 계산이 재귀 함수를 사용한 팩토리얼 계산보다 실행 시간이 더 짧음을 알 수 있습니다.

중첩된 리스트 탐색하기

이제 재귀 함수를 사용하여 중첩된 리스트를 탐색하는 문제를 해결해보겠습니다. 중첩된 리스트는 다른 리스트를 포함하는 리스트를 말합니다. 이러한 리스트를 탐색하기 위해서는 재귀 함수를 사용하는 것이 효과적입니다.

중첩된 리스트 재귀적으로 탐색하기

먼저, 재귀 함수를 사용하여 중첩된 리스트를 재귀적으로 탐색하는 함수를 정의해야 합니다. 다음은 중첩된 리스트를 재귀적으로 탐색하는 함수의 예입니다.

def recursive_list_search(nested_list):
    for item in nested_list:
        if isinstance(item, list):
            recursive_list_search(item)
        else:
            print(item)

중첩된 리스트 반복문으로 탐색하기

다음으로, 중첩된 리스트를 반복문으로 탐색하는 함수를 정의해보겠습니다. 중첩된 리스트를 재귀 함수 대신 반복문을 사용하여 탐색할 수 있습니다.

def iterative_list_search(nested_list):
    stack = [nested_list]
    while stack:
        current = stack.pop()
        if isinstance(current, list):
            stack.extend(current)
        else:
            print(current)

이제 재귀 함수를 사용하여 중첩된 리스트를 탐색하는 방법과 반복문을 사용하여 중첩된 리스트를 탐색하는 방법을 비교해보겠습니다.

nested_list = [1, 2, [3, 4, [5, 6]], [7, 8], 9]

# 재귀 함수를 사용한 중첩된 리스트 탐색
recursive_list_search(nested_list)

print("=====")

# 반복문을 사용한 중첩된 리스트 탐색
iterative_list_search(nested_list)

실행 결과는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
=====
9
[7, 8]
[3, 4, [5, 6]]
2
1

위의 결과를 보면, 재귀 함수를 사용한 중첩된 리스트 탐색과 반복문을 사용한 중첩된 리스트 탐색은 결과가 약간 다르다는 것을 알 수 있습니다.

회문 판별하기

이제 재귀 함수를 사용하여 회문을 판별하는 문제를 해결해보겠습니다. 회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 문장을 말합니다. 이러한 문제는 재귀 함수를 사용하여 쉽게 해결할 수 있습니다.

회문 판별 함수 정의하기

먼저, 재귀 함수를 사용하여 회문을 판별하는 함수를 정의해야 합니다. 다음은 주어진 문자열이 회문인지 아닌지를 판별하는 재귀 함수의 예입니다.

def is_palindrome(word):
    if len(word) <= 1:
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome(word[1:-1])

회문 판별하기

다음으로, 재귀 함수를 사용하여 회문인지 아닌지를 판별해보겠습니다. 다음은 주어진 문자열이 회문인지 아닌지를 판별하는 예입니다.

word1 = "level"
word2 = "python"

print(is_palindrome(word1))  # True
print(is_palindrome(word2))  # False

실행 결과는 다음과 같습니다.

True
False

위의 결과를 보면, 재귀 함수를 사용하여 회문을 판별하는 것이 간단하고 효과적임을 알 수 있습니다.

퀵 정렬로 정렬하기

이제 재귀 함수를 사용하여 퀵 정렬을 구현해보겠습니다. 퀵 정렬은 대표적인 정렬 알고리즘 중 하나로, 재귀 함수를 사용하여 배열을 효율적으로 정렬할 수 있습니다.

피벗 아이템 선택하기

먼저, 퀵 정렬에서 피벗 아이템을 선택하는 방법에 대해 알아보겠습니다. 피벗 아이템은 배열을 분할하는 기준이 되는 아이템입니다. 피벗 아이템의 선택은 배열을 얼마나 효율적으로 정렬할 수 있는지에 영향을 줍니다.

파티셔닝 구현하기

다음으로, 퀵 정렬에서 파티셔닝을 구현해보겠습니다. 파티셔닝은 배열을 피벗을 기준으로 두 개의 하위 배열로 나누는 과정을 말합니다. 이 과정은 재귀적으로 수행되어 배열이 정렬되는 데 사용됩니다.

퀵 정렬 구현하기

이제 파티셔닝을 사용하여 퀵 정렬을 구현해보겠습니다. 다음은 재귀 함수를 사용하여 배열을 퀵 정렬하는 함수의 예입니다.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) https://codemdd.io/ 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

퀵 정렬 사용하기

이제 구현한 퀵 정렬 함수를 사용하여 배열을 정렬해보겠습니다. 다음은 퀵 정렬을 사용하여 배열을 정렬하는 예입니다.

arr = [3, 6, 8, 1, 4, 2, 9, 5, 7]
sorted_arr = quicksort(arr)
print(sorted_arr)

실행 결과는 다음과 같습니다.

[1, 2, 3, 4, 5, 6, 7, 8, 9]

이와 같은 방식으로 재귀 함수를 사용하여 퀵 정렬을 구현할 수 있습니다.

결론

위에서는 재귀 함수를 사용하여 문제를 해결하는 방법에 대해 알아보았습니다. 재귀 함수는 자기 자신을 호출함으로써 작업을 보다 간결하고 자연스럽게 표현할 수 있는 유용한 도구입니다. 여러가지 문제를 해결하는데 재귀 함수를 사용하여 비교적 간단하고 효율적인 솔루션을 구현할 수 있습니다.