재귀란 무엇입니까?

재귀는 함수 호출 자체를 만드는 방법입니다. 아래 다이어그램은 func 함수가 본문에서 자신을 호출하고 있음을 보여줍니다.

def func(): <--
              |
              | (recursive call)
              |
func() --------

재귀 단계 작업

1. 재귀 함수의 구성 요소

무한 반복되는 재귀 함수를 정지시키는 조건을 기본 조건이라고 합니다.

def func(a):    <------------
    if(a < 5):              |
        func(a+1)---------->| (recursive step)
    print(a)                |
func(0) -------------------> (here we are taking a as 0)

위의 함수는 범위( a ~ 5 )의 모든 숫자를 인쇄합니다. 기본 조건이 충족되는 즉시 함수 실행이 중지됩니다. 아래는 출력입니다.

5
4
3
2
1
0

기본 조건을 제거하면 RecursionError 가 발생합니다. 이는 함수를 호출해야 하는 시기에 대한 제한이 없기 때문에 발생합니다. 따라서 동일한 기능을 무한정 반복합니다. 아래 출력을 확인하십시오.

  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

자, 이제 기본 사례와 재귀 단계의 개념을 이해하셨을 것입니다. 예이 😎

2. 재귀 트리

마지막 함수가 종료되면서 첫 번째 재귀 함수도 즉시 종료된다고 생각하면 오산이다.

재귀에서 발생하는 것은 첫 번째 함수가 두 번째 함수를 호출하고 두 번째 함수는 세 번째 함수를 호출하는 식입니다. 상위 함수는 모든 하위 함수가 종료된 경우에만 종료됩니다.

main( ) <--- 
           | (returning to main() function)
func(0) <---
   ↓       |
func(1) <---
   ↓       |
func(2) <---
   ↓       |
func(3) <---
   ↓       |
func(4) ---> (returning to parent function)

위의 다이어그램은 Recursion Tree 로 알려져 있습니다. 재귀를 시각화하는 가장 좋은 방법입니다.

3. 헤드 재귀 vs 테일 재귀

헤드 재귀에서는 먼저 재귀 호출을 수행한 다음 재귀 호출의 반환 값을 가져와 결과를 계산합니다. 꼬리 재귀에서는 먼저 계산을 수행한 다음 재귀 호출을 실행하여 현재 단계의 결과를 다음 재귀 단계로 전달합니다.

다음은 헤드 재귀에 대한 코드입니다.

def headrec(n):
    if(n == 0):
        return
    else:
        headrec(n-1)
    print(n)

다음은 꼬리 재귀에 대한 코드입니다.

def tailrec(n):
    if(n == 1):
        return
    else:
        print(n)
    tailrec(n-1)

예

1. n개의 자연수의 합 계산하기

def recurSum(n):
    if n <= 1:
        return n
    return n + recurSum(n - 1)

print(recurSum(100))

아래 출력은 n(100) 자연수의 합을 보여줍니다.

5050

사용해야 하나 말아야 하나

장점
단점


재귀는 명확성을 더하고 때로는 코드를 작성하는 데 필요한 시간을 줄여줍니다.
재귀 솔루션은 항상 논리적이며 추적하기가 매우 어렵습니다.

재귀는 문제를 쉬운 작은 단계로 나누는 데 도움이 됩니다.
항상 if 조건이 필요합니다.

불필요한 함수 호출을 줄입니다.
재귀는 더 많은 프로세서 시간을 사용합니다.

전체 코드 크기를 줄입니다.
스택 오버플로가 발생할 수 있습니다.



읽어주셔서 감사합니다.🙂