[파이썬 알고리즘] 재귀용법(recursive call, 재귀호출)

재귀용법이란?

함수 안에서 동일한 함수를 호출하는 방법으로 여러 곳에서 응용되니 익숙해져야 할 용법입니다.

재귀 호출의 동작방식은 함수 내부에서의 스택이라고 볼 수 있는데 함수의 결과값 위에 또 다른 결과값을 얹히는 방식으로 알고리즘이 진행됩니다. 그후에 맨 위에 값부터 리터하고 값을 넘겨줍니다. 얹는 과정을 Call function 결과값을 리턴하는 과정을 Returning values 라 했습니다.

실제 코드가 어떻게 돌아가는지 볼 수 있는 사이트가 있는데 아래 링크로 남겨놓겠습니다.
알고리즘의 진행순서가 어떻게 되는지 살펴보시기 바랍니다.
https://pythontutor.com/visualize.html#mode=display

재귀용법의 제한

재귀용법을 무한정 쓸 수 있다면 반복문은 필요하지 않을 수도 있습니다.
하지만 지정된 함수를 계속 쓰게 되면 메모리 과부하가 올수밖에 없습니다. 왜냐하면 재귀호출을 하기 위해서는 재귀용법의 동작방식에서 알 수 있듯이 메모리에 모든 것을 다 넣고 하나씩 해결하기 때문에 유한한 메모리로는 버틸 수 없게 됩니다.
따라서, 파이썬에서는 재귀함수는 한번에 호출되는 횟수(재귀 깊이)가1000회 이하가 되게 설계해주어야 합니다. 즉, 최대 재귀 깊이는 1000 이하여야 합니다.
1000 이상을 할시 아래와 같은 오류가 나타납니다.

 

종료조건 만들기

최대 깊이가 존재하니 제한이 없는 재귀함수를 만들었다면 반드시 종료조건을 만들어주어야 오류없이 동작합니다. while 문구에서 많이쓰는 count 을 세는 방식을 써도 되고(해당 숫자가 되거나 작아지면 멈추라는 명령을 해주는 방식) 문자를 이용해서 멈출 때의 신호를 넣어도 됩니다.

재귀함수에 종료조건을 넣은 간단한 예시입니다.

# 종료조건 넣기
def count_down(count):
    if count == 0:   # count =0 이면 재귀 종료
        return

    print(count)
    count -=1
    count_down(count)

count_down(5)

재귀 용법 예

팩토리얼 만들기

팩토리얼은 $ n! = n(n-1)(n-2)...(2)(1) $ 로 1부터 n까지의 양의 정수의 곱을 말합니다.
확률에서 많이 쓰이는데 이를 코드로 구현하려면 이전 결과값에 새로운 값을 계산하게 됩니다.
즉, 5!을 한다고 하면 코드에서는 4!까지 구한것에 5를 곱하는 방식으로 갑니다.
그러면 4!은 3!이 필요하고 3!은 2!이 필요하게 됩니다. 사실 재귀용법은 반복문으로 모두 해결할 수 있지만 복잡한 문제일 경우는 코드의 이해를 위해 재귀 용법을 쓰게 됩니다. 재귀 용법은 반복문을 안쓰고 함수로 해결하는 것이어서 재귀 용법을 안 쓰는 경우와 쓰는 경우 모두 가능합니다.

# 재귀 용법 안 쓴 경우
def factorial(n):
    return_value = 1
    for num in range(1,n+1):
        return_value = return_value*num
    return return_value

# 재귀 용법을 쓰는 경우
def factorial(n):
    if n<= 1:
        return n    # n=1이면 1 출력
    return n*factorial(n-1)  # n>1 이면 이전 값과 곱해진다.

재귀 용법을 안 쓰는 경우는 for문을 통해서 계속 값을 곱해나가게 하고 재귀용법은 그 과정을 함수를 호출함으로써 해결합니다. 코드를 보면 알겠지만 재귀 용법이 좀 더 간결하고 직관적인 이해가 쉽습니다.

회문(palindrome) 판별하기

회문은 순서를 거꾸로 읽어도 똑같은 단어나 문장을 의미합니다.
예로는 토마토, 마그마, 맨투맨, eye, level 정도 있을 수 있겠네요. 이 또한 알고리즘으로 해결하려고 한다면 재귀용법을 사용하는게 용이합니다. 재귀용법으로 주어진 문장이나 단어가 회문인지 판별할 수 있습니다.

회문은 대칭적으로 글자가 구성되어 있습니다. 맨끝의 글자들부터 비교를 하고 비교가 완료되면 제외시키는 방식으로 접근할 수 있습니다. 그런데 회문이 길이가 정해져있지 않기 때문에 반복문으로는 약간 구현하기 까다롭습니다.
양 끝을 하나씩 빼고 다시 회문 판별을 하는 방식으로 하려면 재귀용법이 아주 용이합니다.

def criteria_palindrome(word):
    if len(word) <=1:
            return True
    if word[0] == word[-1]:
            return criteria_palindrome(word[1:-1]) #문자열 슬라이싱으로 양끝의 문자 제외 후 재귀호출
    else:
        return False

회문이 맞다면 True 아니라면 False를 반환합니다.

word1 = 'level'
word2 = 'abcd'
print(criteria_palindrome(word1),criteria_palindrome(word2))

마치며

재귀용법은 보기엔 쉬워보이지만 막상 해볼려고 하면 잘 안되는 방법 중 하나입니다.
다른 사람의 짜놓은 알고리즘 코드를 봤을 때 '이거 재귀용법이구나' 는 생각이 든다면 적어도 재귀용법을 이해한거라 봅니다. 많은 연습과 시행착오가 필요합니다.

 

함께 보면 좋은 글

[자료구조] 스택(Stack)

[Python] 문자열(string) 다루기

[Python] 속도개선 -알고리즘편(Recursive)