Python Recursive Functions: 재귀 함수란

이 자습서에서는 Python 재귀 함수와 이를 사용하여 코드를 단순화하는 방법에 대해 배웁니다.

 

1. recursive functions: 재귀 함수 소개

재귀 함수는 호출되지 않을 때까지 자신을 호출하는 함수입니다.

다음 fn() 함수는 자신을 호출하기 때문에 재귀 함수입니다.

def fn():
    # ...
    fn()
    # ...

fn() 함수에서 #...은 다른 코드를 의미합니다.

 

또한 재귀 함수는 자신을 호출하지 않는 조건이 있어야 합니다. 따라서 다음과 같은 if 문을 추가해야 합니다.

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...

 

일반적으로 재귀 함수를 사용하여 해결하기 어려운 큰 문제를 해결하기 쉬운 작은 문제로 나눕니다.

 

프로그래밍에서 트리, 그래프 및 이진 검색과 같은 데이터 구조 및 알고리즘에 사용되는 재귀 함수를 자주 찾을 수 있습니다.

 

 

2. 파이썬 재귀 함수 예제

Python 재귀 함수를 사용하는 몇 가지 예를 들어 보겠습니다.

 

1) Python의 간단한 재귀 함수 예제

지정된 숫자에서 0까지 카운트다운하는 카운트다운 함수를 개발해야 한다고 가정합니다.

 

예를 들어 3부터 카운트다운하는 함수를 호출하면 다음과 같은 출력이 표시됩니다.

3
2
1

 

다음은 count_down() 함수를 정의합니다.

def count_down(start):
    """ Count down from a number  """
    print(start)

 

지금 count_down() 함수를 호출하면:

count_down(3)

...숫자 3만 표시됩니다.

 

숫자 3, 2, 1을 표시하려면 다음을 수행해야 합니다.

• 먼저 count_down(3)을 호출하여 숫자 3을 표시합니다.
• 둘째, count_down(2)을 호출하여 숫자 2를 표시합니다.
• 마지막으로 count_down(1)을 호출하여 숫자 1을 표시합니다.
       

이렇게 하려면 count_down() 함수 내에서 인수 2와 1로 count_down() 함수를 호출하는 논리를 정의해야 합니다.

 

이를 위해서는 count_down() 함수를 재귀적으로 만들어야 합니다.

 

다음은 재귀 count_down() 함수를 정의하고 숫자 3을 전달하여 호출합니다.

def count_down(start):
    """ Count down from a number  """
    print(start)
    count_down(start-1)


count_down(3)

 

프로그램을 실행하면 다음 오류가 표시됩니다.

RecursionError: maximum recursion depth exceeded while calling a Python object

그 이유는 count_down()이 시스템이 중지할 때까지 무한정 자신을 호출하기 때문입니다.

카운트 다운을 중지해야 하므로 숫자가 0이 됩니다. 이렇게 하려면 다음과 같은 조건을 추가합니다.

def count_down(start):
    """ Count down from a number  """
    print(start)

    # call the count_down if the next
    # number is greater than 0
    next = start - 1
    if next > 0:
        count_down(next)


count_down(3)

 

Output:

3
2
1

 

이 예제에서 count_down() 함수는 다음 숫자가 0보다 클 때만 자신을 호출합니다. 즉, 다음 숫자가 0이면 자신을 호출하지 않습니다.

 

2) 재귀 함수를 사용하여 시퀀스의 합 계산

예를 들어 1에서 100까지 시퀀스의 합계를 계산해야 한다고 가정합니다. 이를 수행하는 간단한 방법은 range() 함수와 함께 for 루프를 사용하는 것입니다.

def sum(n):
    total = 0
    for index in range(n+1):
        total += index

    return total


result = sum(100)
print(result)

 

Output:

5050

재귀 기법을 적용하려면 다음과 같이 1에서 n까지의 시퀀스 합을 계산할 수 있습니다.

• sum(n) = n + sum(n-1)
• sum(n-1) = n-1 + sum(n-2)
• …
• sum(0) = 0

 

sum() 함수는 인수가 0보다 큰 한 계속 자신을 호출합니다.

다음은 sum() 함수의 재귀 버전을 정의합니다.

def sum(n):
    if n > 0:
        return n + sum(n-1)
    return 0


result = sum(100)
print(result)

 

보시다시피 재귀 함수는 훨씬 더 짧고 읽기 쉽습니다.

삼항 연산자를 사용하면 sum()이 훨씬 더 간결해집니다.

def sum(n):
    return n + sum(n-1) if n > 0 else 0


result = sum(100)
print(result)

 

3. Summary

• 재귀 함수는 호출되지 않을 때까지 자신을 호출하는 함수입니다.
• 그리고 재귀 함수에는 항상 자기 호출을 중지하는 조건이 있습니다.
       

 

 

 

refreance: https://www.pythontutorial.net/python-basics/python-recursive-functions/