문제가 더 작은 조각으로 계속 분기되는 끝이 없어 보이는 주기에 갇힌 적이 있습니까?
그렇다면 매력적인 재귀의 세계를 접하셨을 것입니다. 이해하기 어려워 보일 수 있지만 걱정하지 마십시오! 이 게시물에서는 재귀 유형에 대해 알아보는 흥미로운 여정을 진행합니다.
그러니 우리가 수많은 재귀적 접근법을 탐구할 때 버클을 채우십시오. 매력적인 재귀 영역에 들어갈 준비를 하고 복잡한 문제를 해결하는 놀라운 능력을 관찰하십시오.
재귀란 정확히 무엇입니까?
기본적으로 재귀는 실행 중에 자신을 호출하는 함수를 포함하는 강력한 프로그래밍 기술입니다. 그것은 거울을 응시하고 이미지 안의 이미지를 보는 것과 같으며 결과적으로 자기 참조 순환이 발생합니다.
재귀를 사용하여 더 작고 관리하기 쉬운 하위 문제로 나누어 큰 문제를 해결할 수 있습니다.
하나의 조각이 다른 부분과 연결되어 전체 그림을 생성하는 직소 퍼즐을 맞추는 것과 비슷합니다. 재귀를 사용하면 다양한 입력으로 동일한 명령 세트를 반복하여 우아하고 효율적인 방식으로 문제를 해결할 수 있습니다.
1-직접 재귀
직접 재귀는 함수가 자신을 직접 호출하는 가장 기본적인 재귀 유형입니다. 기본 사례가 달성될 때까지 문제가 있는 문제를 더 작은 하위 문제로 나누어 종료로 이어집니다.
재귀 함수는 다양한 입력으로 자신을 호출하여 동일한 명령 세트를 반복하여 실행할 수 있습니다. 각 호출은 이전 호출을 기반으로 하며 재귀를 종료시키는 기본 사례에 점진적으로 가까워집니다.
이 예를 확인해 봅시다.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
출력:
5
4
3
2
1
2-간접 재귀
간접 재귀는 재귀 경로에 흥미로운 반전을 추가합니다. 자신을 명시적으로 호출하는 함수를 포함하는 직접 재귀와 달리 간접 재귀에는 일련의 함수 호출이 포함됩니다.
한 함수가 다른 함수를 호출하면 원래 함수를 호출하거나 최종적으로 원래 함수로 돌아가는 다른 함수를 호출할 수 있습니다. 이 상호 연결된 함수 호출 웹은 여러 함수가 협력하여 문제를 해결하는 매혹적인 춤을 만들어냅니다.
예:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
출력:
A: 3
B: 2
A: 1
3-선형 재귀
목표에 도달할 때까지 한 번에 한 걸음씩 직선 경로를 따라 여행하는 것을 고려하십시오. 이 순차 기술은 함수가 각 함수 반복에서 단일 재귀 호출을 수행하는 선형 재귀로 구현됩니다.
재귀 호출이 있을 때마다 재귀 프로세스는 문제 크기를 줄임으로써 기본 사례에 더 가깝게 이동합니다. 최종 답에 도달할 때까지 하위 문제를 한 번에 하나씩 해결하면서 명확하고 선형적인 방식으로 진행됩니다.
예:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
출력:
120
4-트리 재귀
함수가 여러 재귀 호출로 분기되면 트리 재귀의 세계로 들어갑니다. 트리 재귀 함수는 많은 재귀 호출을 생성하며 각 호출은 트리의 가지처럼 별도의 하위 문제를 해결합니다.
이 분기 구조를 통해 여러 경로를 동시에 조사할 수 있으므로 복잡한 문제를 더 작고 상호 관련된 구성 요소로 효과적으로 분류할 수 있습니다.
예:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
출력:
8
5-중첩 재귀
중첩된 재귀는 재귀적 세계에 흥미진진한 복잡성을 더합니다. 이 형태의 재귀에서 함수는 재귀 호출을 다른 재귀 호출 내의 인수로 통합합니다.
내부 재귀 호출은 외부 재귀 호출에 종속된 값에 대해 작동합니다. 복잡성은 각각의 중첩된 호출과 함께 증가하여 중첩된 재귀 호출의 흥미로운 패턴으로 절정에 이릅니다.
예:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
결과 :
91
6-꼬리 재귀
꼬리 재귀는 재귀 알고리즘의 성능을 향상시킬 수 있는 최적화 기술입니다. 재귀 호출은 꼬리 재귀가 있는 함수의 마지막 동작으로 나타납니다.
재귀 호출 뒤에는 미해결 작업이 없기 때문에 컴파일러나 인터프리터는 재귀를 간단한 점프로 대체하여 단순화할 수 있습니다.
꼬리 호출 최적화로 알려진 이 최적화 접근 방식은 스택 프레임을 유지하기 위한 각 재귀 호출의 요구 사항을 줄여 속도를 높이고 메모리 사용량을 줄입니다.
예:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
아웃아웃:
120
7 꼬리가 아닌 재귀
테일 재귀와 달리 비테일 재귀에는 함수 내에서 재귀 호출 후에 수행되는 추가 활동이 포함됩니다. 추가 작업을 수행하기 전에 각 재귀 호출이 완료되고 반환되어야 합니다.
결과적으로 기본 사례에 도달하고 재귀가 끝날 때까지 미해결 작업 스택이 유지됩니다. Non-tail 재귀는 종종 더 많은 메모리를 사용하고 tail 재귀보다 덜 효율적이지만 여전히 다양한 문제를 해결하는 데 유용한 도구입니다.
예:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
출력:
15
마무리
재귀는 프로그래밍에서 흥미로운 개념입니다. 재귀적이고 자기 참조적인 방식으로 복잡한 문제를 해결할 수 있습니다.
그것은 문제에 대해 생각하고 해결하는 독특한 방법을 제공하여 문제를 더 작고 관리하기 쉬운 덩어리로 나눕니다. 그러나 재귀를 사용할 때는 몇 가지 사항에 주의를 기울여야 합니다.
재귀를 종료할 수 있는 적절한 기본 사례를 식별해야 합니다. 존재하지 않는 경우 함수는 계속해서 자신을 계속 호출할 수 있습니다.
둘째, 당면한 시나리오를 기반으로 적절한 종류의 재귀를 선택하면 보다 효율적이고 우아한 솔루션으로 이어질 수 있습니다. 손의 문제에 가장 적합한 것을 찾으십시오. 방대한 재귀 깊이로 작업할 때 스택 오버플로와 같은 잠재적인 위험에 주의하세요.
댓글을 남겨주세요.