[알고리즘] Python 재귀함수

안녕하세요

알고리즘 공부를 하면서 블로그에 정리를 할려고 하는데요

Java를 공부하면서 알고리즘 파이썬을 하다니... 파이썬이 쉬우니깐요 ^^

그래도 알고리즘은 어렵습니다. 한개한개 미션 클리어 하는 느낌으로 블로그를 작성해볼게요

---

파이썬 재귀함수

파이썬에서 사용하는 함수는 아니고요. 모든 프로그래밍 언어에서 함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 합니다. 재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용합니다. 예를 들어서 DFS(깊이 우선 탐색) 이라던가 집합의 합이라던가 팩토리얼 등 다양한 곳에 사용을 할 수가 있습니다.

재귀함수 사용

간단하게 재귀호출 함수를 만들어 보겠습니다.

def hello():
    print("Hello!!")
    hello()


hello()

hello 함수 안에서 다시 hello  함수를 호출하고 있습니다.
소스 코드를 실행해보면 'Hello!!' 문자열이 계속 출력되다가 에러가 발생합니다. 이유는 파이썬에서 최대 재귀 깊이(maximum recursion depth)가 1000으로 정해져 있어서 그렇습니다. 즉, hello 함수가 자기 자신을 계속 호출하다가 최대 재귀 깊이를 초과하면 RecursionError 가 발생합니다.

종료조건을 만들어주기

def hello(count):
    if count == 0:
        return

    print("Hello!!", count, "번 남았습니다.")

    count -= 1
    hello(count)


hello(5)

<결과화면>

먼저 hello 함수의 반복 횟수를 계산하기 위해서 매개 변수 count를 지정합니다. 그리고 count가 0이면 hello 함수를 종료시킵니다. 만약 0이 아니면 출력문을 출력하고 count의 값을 1씩 감소시킨 뒤 hello 함수를 호출할 때 넣어줍니다.

재귀함수를 사용할때는 종료 조건을 추가해줍니다!!

팩토리얼 예제

재귀함수 없이 팩토리얼 구현

팩토리얼 5! 이라고 하면 5 x 4 x 3 x 2 x 1 = 120 입니다.

def factorial(n):
    f = 1
    for i in range(n, 0, - 1):
        f *= i
    return f


print(factorial(5))

120

재귀함수를 사용해서 팩토리얼을 구현

일단 함수의 최소값일때 return 하는 부분을 먼저 만들어 주어야합니다.(종료값없으면 RecursionError 오류가 발생)

1! = 1
2! = 2 x 1!
3! = 3x2!
4! = 4x3!
n! = nx(n-1)!

이런 순서로 이루어져 있다. factorial 함수를 재구성 해보도록 하자

def factorial(n):
    if n == 1:
        return 1

    result = n * factorial(n-1)
    return result


print(factorial(5))

---

※참고※

https://shoney.tistory.com/entry/Python-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98-%EA%B0%84%EB%8B%A8%EC%98%88%EC%A0%9C-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-%EA%B5%AC%ED%98%84
https://dojang.io/mod/page/view.php?id=2352