Python 재귀함수

만약 N개의 줄에 걸쳐서 hello world를 출력하는 코드를 함수를 이용하여 작성한다면 다양한 방법이 있다.

N = int(input())

def func():

    for i in range(N):

        print("hello world")

func()

위와 같이 한번의 함수 호출에서 반복문을 사용하여 출력하게 할 수 있고

N = int(input())

def func(N):

    if N == 0:

        return

    func(N- 1)

    print("hello world")

func(N)

위와 같이 함수 내부에서 함수를 다시 호출하여 한번의 함수 호출마다 한번씩 출력되게 작성할 수 있다.

위와 같은 구조(호출한 함수 내부에서 호출한 함수를 다시 호출)로 작성된 함수를 재귀함수라고 한다.

재귀함수를 사용할때는

    if N == 0:

        return

해당하는 코드를 작성하여 함수의 종료지점을 설정해줘야 한다.  해당 코드가 누락할 시 함수가 무한적으로 호출되기

때문에 RecursionError: maximum recursion depth exceeded 오류가 발생한다

 

재귀함수에서는 함수 재호출과 출력 순서가 중요하다

def plus(N):

    if N == 0:

        return

    plus(N - 1)    

    print(N, end = " ")

   

def minus(N):

    if N == 0:

        return

    print(N, end = " ")

    minus(N - 1)

N = int(input())

plus(N)

print()

minus(N)

위의 코드는 plus와 minus가 각각 출력과 호출 순서만 다르지만 5 입력시 아래의 결과가 나온다.

1 2 3 4 5 
5 4 3 2 1

호출, 출력 순서에 따라 코드가 정 반대로 동작할 수 있기 때문에 이점을 주의해서 코드를 작성해야 한다.

위에서 사용했던 재귀함수는 단순히 출력만 하는 재귀함수이다.

 

def fact(n):

    if n == 1:

        return 1

    return fact(n - 1) * n

print(fact(5))

이처럼 반환형이 있는 재귀함수로 작성할 수 있다. 위 코드는 1부터 n까지의 곱을 구하는 팩토리얼 함수이다.

def func(N):

    if N == 1:

        return 1

    if N == 2:

        return 1

   

    return func(N - 1) + func(N - 2)

N = int(input())

print(func(N))

위의 코드는 반환형 재귀함수를 활용하여 피보나치 수열을 구현한 코드이다.