CodeGym /행동 /Python SELF KO /재귀의 개념

재귀의 개념

Python SELF KO
레벨 57, 레슨 0
사용 가능

1.1 재귀의 정의와 주요 개념들

재귀는 무언가가 스스로를 계속 반복하는 걸 말해. 예를 들어, 어떤 명령이 있고 그 명령의 일부가 그 명령을 따르라는 거라면, 그게 바로 재귀야. 마치 명령을 자기 자신에게 반복하라는 것처럼.

일상 생활의 예:

거울 맞대기:

두 거울 사이에 서 있다고 상상해봐. 너는 자신의 반영을 보고, 그 반영 안에서도 또 다른 반영을 보게 돼. 이게 계속 반복되지. 이게 바로 재귀야, 왜냐면 각 거울이 다른 거울의 반영을 보여주니까.

마트료시카:

마트료시카는 내부에 또 다른 인형이 있고, 그 안에 또 다른 인형이 있는 그런 인형이야. 가장 작은 인형에 도착하면 더 이상 열 것이 없지. 이게 바로 재귀의 기본 사례 - 멈춰야 할 때와 같아.

피자 나누기:

피자를 반으로 나눈다고 상상해봐. 그런 다음 또 반을 나누고, 계속해서 피스가 너무 작아져서 나눌 수 없을 때까지. 나누는 과정이 재귀적 프로세스고, 더 이상 나눌 수 없을 때의 순간이 기본 사례야.

중요해! 재귀는 무한 반복이 아니야. 오히려 복잡한 문제를 작은 문제로 나누면서, 작은 문제의 해결 방법이 원래 문제의 해결 방법과 비슷한 경우를 말해.

어떻게 작동하는 거야?

재귀를 이해하려면 두 가지 주요 개념을 알아야 해:

  • 기본 사례: 재귀가 멈추는 조건이야. 예를 들어 마트료시카의 경우, 가장 작은 인형을 열었을 때 더 이상 아무것도 없는 경우가 기본 사례야.
  • 재귀적 사례: 문제를 더 작은 부분으로 나눠서 계속 진행하는 거야. 피자 예시에서 너는 조각을 나누고, 그러고 나서 반을 나누고, 계속해서 비슷한 방식으로 진행해.

왜 유용할까?

재귀는 복잡한 문제를 더 간단한 부분으로 나누어 해결을 도와줘. 문제를 한꺼번에 해결하는 대신 조각난 부분을 해결하는 거야.

다른 삶의 예:

이야기 속 이야기:

동화 속 주인공이 또 다른 이야기를 하고, 그 이야기 속 주인공이 다시 또 다른 이야기를 한다고 상상해봐. 이야기가 끝나면 이전 이야기로 돌아가게 돼. 기본 사례는 마지막 이야기가 끝나는 거야.

재귀적 그림:

큰 삼각형을 그린 다음, 그 모서리 각 부분에 작은 삼각형을 그려. 그리고 삼각형이 너무 작아져서 그릴 수 없을 때까지 계속해. 기본 사례는 삼각형이 너무 작아져서 더 이상 그릴 수 없는 거야.

1.2 기본 사례: 정의와 예

기본 사례는 함수가 구체적인 값을 반환할 수 있는 재귀적 호출을 종료하는 조건이야. 일반적으로 가장 간단하고 명확한 문제의 해결책이지, 추가적인 재귀가 필요하지 않아.

기본 사례의 예:

숫자의 팩토리얼:

숫자 n의 팩토리얼은 F(n) == 1*2*3*…*n로 표시돼. 그리고 F(n) == n* F(n-1)인 것도 명확해.

기본 사례: 숫자 0 또는 1의 팩토리얼은 1이야. F(0) == F(1)==1


def factorial(n):
    if n == 0 or n == 1:
        return 1  # 기본 사례
    else:
        return n * factorial(n - 1)
        

피보나치 수열:

피보나치 수열은: 1, 1, 2, 3, 5, 8, 13, … 처럼 되어 있어. 각 다음 숫자는 두 이전 숫자의 합이야. F(n) == F(n-1) + F(n-2)

기본 사례: 첫 두 피보나치 숫자는 1이야, 그래서 "0번째" 피보나치 숫자는 0이야. 또는 F(0) = 0 및 F(1) = 1.


def fibonacci(n):
    if n == 0:
        return 0  # 기본 사례
    elif n == 1:
        return 1  # 기본 사례
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 재귀적 사례: 정의와 예

재귀적 사례는 함수의 일부로, 문제를 새로운 매개변수로 자기 자신을 호출하면서 해결하는 거야. 그로써 문제 해결을 기본 사례에 점점 다가가게 만들어. 각 재귀적 호출은 문제를 축소하거나 수정해서 결국 기본 사례에 도달하게 해.

재귀적 사례의 예:

숫자의 팩토리얼:

재귀적 사례: 숫자 n의 팩토리얼은 n 곱하기 숫자 n-1의 팩토리얼이야.


def factorial(n):
    if n == 0 or n == 1:
        return 1  # 기본 사례
    else:
        return n * factorial(n - 1)  # 재귀적 사례
        

피보나치 수열:

재귀적 사례: F(n)은 F(n-1)과 F(n-2)의 합이야.


def fibonacci(n):
    if n == 0:
        return 0  # 기본 사례
    elif n == 1:
        return 1  # 기본 사례
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 재귀적 사례
        

1.4 재귀적 알고리즘의 예

1. 이진 트리 순회:

"in-order" 순회의 예.


class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# 사용 예:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. 리스트에서 최대 원소 찾기:


def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # 기본 사례
    else:
        max_of_rest = find_max(lst[1:])  # 재귀적 사례
        return max(lst[0], max_of_rest)
        
# 사용 예:
print(find_max([1, 5, 3, 9, 2]))  # 출력: 9
        
        

3. 재귀적 이진 검색:


def binary_search(arr, target, left, right):
    if left > right:
        return -1  # 기본 사례: 요소를 찾지 못함
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # 기본 사례: 요소를 찾음
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # 재귀적 사례
    else:
        return binary_search(arr, target, left, mid - 1)  # 재귀적 사례 
# 사용 예:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # 출력: 4
        
코멘트
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION