[Python]파이썬 함수 활용하기: 재귀 함수부터 리스트 평탄화까지

python 재귀 함수는 자기 자신을 호출하여 문제를 해결하는 데에 사용됩니다. 이를 통해 코드의 간결성과 가독성을 높일 수 있습니다. python 재귀 함수를 사용하여 팩토리얼, 피보나치수열, 그리고 리스트 평탄화를 구현하는 방법에 대해 알아보겠습니다.

≣ 목차

• 재귀함수🎡
• 팩토리얼 구하기🎲
• 피보나치 수열 구현👨‍❤️‍👨👨‍❤️‍👨👨‍👩‍👧‍👦👩‍👦‍👦👨‍👦‍👦
• 메모화📌
• 리스트 평탄화👜
• 핵심 내용👀

---

1. 재귀함수🎡

재귀 함수에서 기본 단계와 재귀 단계는 문제를 해결하는데 중요한 개념입니다.

• 기본 단계(base case) : 기본 단계는 재귀 함수에서 무한 반복을 막기 위한 중요한 요소입니다. 함수가 더 이상 자신을 호출하지 않고 종료되는 조건을 말합니다. 기본 단계를 통해 재귀 함수가 끝나고 결과를 반환할 수 있습니다.
• 재귀 단계(recursive case) : 재귀 단계는 재귀 함수에서 자기 자신을 호출하여 문제를 해결하는 과정을 말합니다. 이 과정에서는 주어진 문제를 더 작은 하위 문제로 나누고, 이 하위 문제를 해결하기 위해 재귀적으로 자기 자신을 호출합니다. 이 과정은 기본 단계에 도달할 때 까지 반복됩니다.

위 두 가지 단계를 팩토리얼을 구하는 예제를 통해 확인해 보겠습니다.

🙌 여기서 잠깐!

팩토리얼이란?

양의 정수 n에 대해 n!로 표현되며, n부터 1까지의 모든 양의 정수를 곱한 값입니다.

간단히 말해 n!은 1부터 n까지의 모든 양의 정수를 곱한 값입니다.

예를 들어, 5의 팩토리얼은 5! = 5 x 4 x 3 x 2 x 1 = 120입니다.

# 재귀 함수를 사용하여 팩토리얼을 계산하는 함수
def factorial_recursive(n):
    # 기본 단계: n이 0일 때 1을 반환하여 재귀 호출을 멈춤
    if n == 0:
        return 1
    # 재귀 단계: n에 대한 팩토리얼을 n-1에 대한 팩토리얼과 곱하여 반환
    else:
        return n * factorial_recursive(n - 1)

# 팩토리얼 계산 예제
print(factorial_recursive(5))  # 출력: 120

---

2.팩토리얼 구하기🎲

팩토리얼 계산에서는 반복문을 사용하는 방법과 재귀 함수를 사용하는 방법이 있습니다.

두 가지 접근 방식의 차이를 이해하기 위해 예제를 통해 확인해 보겠습니다.

# 반복문을 사용하여 팩토리얼을 계산하는 함수
def factorial_iterative(n):
    result = 1  # 결과를 저장할 변수 초기화
    for i in range(1, n + 1):  # 1부터 n까지 반복
        result *= i  # 각 숫자를 차례로 곱하여 결과에 누적
    return result  # 최종 결과 반환

# 재귀함수를 사용하여 팩토리얼을 계산하는 함수
def factorial_recursive(n):
    # 기본 단계: 0! = 1
    if n == 0:
        return 1
    # 재귀 단계: n! = n * (n-1)!
    else:
        return n * factorial_recursive(n - 1)

# 팩토리얼 계산 예제
print(factorial_iterative(5))  # 출력: 120
print(factorial_recursive(5))  # 출력: 120

위 예제를 통해 한 가지 문제를 해결하는 다양한 알고리즘이 존재한다는 것을 이해할 수 있습니다.

재귀 함수와 반복문은 같은 문제를 해결하지만, 각각의 방식은 실행 속도나 메모리 사용 등에서 차이가 있을 수 있습니다.

일반적으로 팩토리얼 계산에서는 반복문을 사용한 방법이 재귀 함수를 사용한 방법보다 효율적입니다.

재귀 함수를 사용하면 함수 호출 시마다 스택에 호출 정보가 저장되므로, 메모리 사용량이 더 많아집니다. 반면에 반복문을 사용하면 추가적인 메모리를 사용하지 않고도 동일한 작업을 수행할 수 있습니다.

일반적으로 재귀 함수는 함수 호출에 따른 오버헤드가 발생하기 때문에 반복문보다 느릴 수 있습니다. 특히 팩토리얼과 같은 간단한 계산에서는 재귀 함수가 반복문보다 더 많은 시간이 소요될 수 있습니다.

따라서 효율적인 알고리즘을 선택한다면, 팩토리얼 계산에서는 반복문을 사용하는 것이 좋습니다.

그러나 재귀 함수를 사용한 알고리즘도 문제를 해결하는 데에는 적합할 수 있으며, 알고리즘의 특성과 문제의 복잡성에 따라 다른 선택이 필요할 수 있습니다.;

---

3.피보나치 수열 구현👨‍❤️‍👨👨‍❤️‍👨👨‍👩‍👧‍👦👩‍👦‍👦👨‍👦‍👦

피보나치수열은 첫 번째 항과 두 번째 항이 각각 1이며, 그 뒤의 모든 항은 바로 앞의 두항을 더하여 만들어지는 수열입니다. 아래 그림을 통해서 피보나치수열의 규칙을 확인해 보겠습니다.

그림에서 각 줄은 피보나치 수열의 각 항을 나타냅니다. 각 항은 바로 앞의 두항을 더한 값입니다.

피보나치 수열은 자연스럽게 재귀적인 특성을 가지고 있습니다. 각 항은 이전 두 항을 더한 값이므로, 이를 재귀적으로 계산하는 것이 직관적입니다. 그럼 예제로 살펴볼까요?

# 피보나치 수열을 재귀함수로 계산하는 함수
def fibonacci_recursive(n):
    # 기본 단계: 첫 번째와 두 번째 항은 각각 0과 1
    if n = 1:
        return n
    # 재귀 단계: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# 피보나치 수열 계산 예제
for i in range(10):
    print(fibonacci_recursive(i), end=" ")  # 출력: 0 1 1 2 3 5 8 13 21 34

재귀 함수를 사용하여 피보나치수열을 계산할 때, 동일한 값이 여러 번 계산되는 경우가 많습니다.

위의 예제에서는 피보나치 수열을 계산하는 과정을 재귀 함수를 사용하여 시각화하였습니다.

하지만 재귀 함수를 사용할 경우, 수열의 값이 계산되는 과정에서 중복 계산이 많이 발생하고, 함수 호출이 지수적으로 증가하여 수열의 일부만을 계산하는 경우에도 계산 시간이 매우 길어질 수 있습니다.

따라서 위의 예제에서는 피보나치 수열의 값이 너무 많아지는 것을 방지하기 위해 3번째 수열까지 만을 구해보았습니다.

이렇게 함으로써 수열이 어떻게 형성되는지를 간단하게 확인할 수 있었습니다.

재귀 함수를 사용하여 피보나치 수열을 계산할 경우, 함수 호출이 지수적으로 증가합니다.

F(n)을 계산할 때 F(n-1)과 F(n-2)를 계산해야 하므로, 함수 호출 횟수는 2ⁿ에 비례합니다.

따라서 n이 커질수록 계산 시간이 급격하게 증가합니다.

이러한 이유들로 인해 피보나치 수열을 재귀적인 방식으로 계산할 때 시간이 오래 걸릴 수 있습니다.

---

4. 메모화📌

피보나치수열을 계산할 때는 중복 계산을 피하기 위해 메모이제이션 기법 즉, 메모화를 사용합니다.

이를 통해 동일한 값을 반복적으로 계산하는 것을 방지하고, 계산 효율성을 높일 수 있습니다.

# 메모화를 사용하여 중복 계산을 피하는 피보나치 수열 함수
memo = {}  # 결과를 저장할 메모이제이션 딕셔너리
def fibonacci_memo(n):
    if n = 1:  # 기본 단계: n이 0 또는 1일 때
        return n
    if n not in memo:  # 메모이제이션: 결과가 아직 저장되지 않았을 경우
        # n-1과 n-2의 피보나치 수를 재귀적으로 계산하여 더한 후, 결과를 메모이제이션
        memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
    return memo[n]  # 메모이제이션된 결과 반환

# 피보나치 수열 계산 예제 (메모화 사용)
for i in range(10):
    print(fibonacci_memo(i), end=" ")  # 출력: 0 1 1 2 3 5 8 13 21 34

1. memo = {}: 결과를 저장할 딕셔너리를 선언합니다. 이 딕셔너리는 이미 계산된 피보나치수열의 값들을 저장하는 데 사용됩니다.
2. def fibonacci_memo(n):: 피보나치 수열을 계산하는 함수를 정의합니다. 이 함수는 인자 n에 대해 피보나치수열의 값을 반환합니다.
3. if n <= 1:: 기본 단계(base case)를 처리합니다. 만약 n이 0 또는 1이면, 해당 값 그대로 반환하고 재귀 호출을 멈춥니다.
4. if n not in memo:: 메모이제이션을 위한 조건문입니다. 만약 현재 계산하려는 피보나치수열의 값이 이미 메모이제이션된 결과에 없다면, 재귀적으로 계산하여 메모이제이션된 결과를 딕셔너리에 저장합니다.
5. memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2): 현재 계산하려는 피보나치수열의 값을 재귀적으로 계산합니다. 이때, 이미 메모이제이션된 값이 있다면 해당 값을 사용하여 중복 계산을 피합니다.
6. return memo[n]: 메모이제이션된 결과를 반환합니다.
7. for i in range(10):: 피보나치 수열의 처음 10개 값을 계산하기 위한 반복문을 설정합니다.
8. print(fibonacci_memo(i), end=" "): 각 인덱스에 대해 계산된 피보나치수열의 값을 출력합니다.

---

5. 리스트 평탄화👜

리스트 평탄화는 중첩된 리스트를 하나의 평탄한(1차원) 리스트로 만드는 작업을 말합니다.

예를 들어, [1, 2, [3, 4], [5, [6, 7]]]와 같은 중첩된 리스트가 있을 때, 이를 [1, 2, 3, 4, 5, 6, 7]과 같이 평탄한 리스트로 만드는 것입니다.

리스트 평탄화는 재귀적인 문제입니다. 리스트 안에 또 다른 리스트가 포함될 수 있고, 이러한 중첩된 리스트를 평탄화하여 하나의 단일한 리스트로 만드는 작업은 재귀적인 접근이 적합합니다.

def flatten_list(lst):
    """
    중첩된 리스트를 평탄화하는 함수
    
    Parameters:
        lst (list): 평탄화할 리스트
        
    Returns:
        list: 평탄화된 리스트
    """
    flattened = []  # 평탄화된 리스트를 저장할 변수 초기화
    for item in lst:  # 리스트의 각 요소에 대해 반복
        if isinstance(item, list):  # 요소가 리스트인지 확인
            flattened.extend(flatten_list(item))  # 리스트면 재귀적으로 평탄화하여 추가
        else:
            flattened.append(item)  # 리스트가 아니면 그대로 추가
    return flattened  # 평탄화된 리스트 반환

example_list = [1, 2, [3, 4, [5, 6]], 7, [8, [9, 10]]]  # 평탄화할 예제 리스트
print(flatten_list(example_list))  # 출력: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

1. flatten_list 함수는 중첩된 리스트를 받아서 평탄화된 리스트를 반환합니다.
2. 함수는 반복문을 사용하여 리스트의 각 요소를 확인합니다.
3. 요소가 리스트인 경우에는 재귀적으로 flatten_list 함수를 호출하여 평탄화한 결과를 추가합니다.
4. 요소가 리스트가 아닌 경우에는 그대로 결과 리스트에 추가합니다.
5. 최종적으로 평탄화된 리스트를 반환합니다.

이 함수는 재귀적인 방식으로 중첩된 리스트를 모두 펼쳐서 하나의 단일한 리스트로 만듭니다.

---

6. 핵심 내용👀