파이썬 함수편2 - 재귀함수(팩토리얼, 피보나치 수열)

파이썬 재귀함수

안녕하십니까 Hun!입니다!

저번에 함수편1에서 함수에 대해서 간략하게 설명하였습니다. 오늘 이번 시간에는 함수에 쓰이는 기법 중 하나인 재귀함수와 함수에 대해서 소개하고자 합니다. 재귀함수(Recursive Function)는 "원래 자리로 다시 되돌아온다"라는 의미의 '재귀'를 응용한 함수기법으로 정해진 규칙에 의해서 반복되는 구조를 표현하여 사용할때 쓰이곤 합니다. 즉 어떤 작업을 수행하는 함수 하나를 만들었는데 그 함수 본문에서 함수 자기자신을 다시 호출하여서 함수를 실행도록 하는 것입니다. 

저는 겹겹이 쌓여서 실행되는 재귀함수를 보고 순간 한번 걸리면 연쇄적으로 일어나는 바둑의 '축' 기술이 생각났는데 초등학교 바둑 동아리에서 고수를 상대로 이기고 있다고 방심하다가 역전 패로 졌던 추억이 떠오르기도 하였습니다. 단, 재귀함수을 사용할 때 필요한 조건이 있습니다. 그 조건은 재귀함수에 최소한 하나는 재귀호출을 멈출 수 있는 조건인 기준이 있어야 한다는 것입니다. 계속 끝 없이 수행되다가는 결과를 확인할 수 없기 때문입니다. 재귀함수의 예시를 들면 저는 다들 고등학교 수학 시간때 배우신 팩토리얼로 사용해 보았습니다.

def factorial(n):

    if n == 0:

        return 1

    else:

        return n * factorial(n - 1)

위의 'factorial' 함수가 팩토리얼을 표현한 함수로 매개변수 n에 인수를 받아서 if-else 조건에 따라서 처리합니다. 만약 인수로 7을 받았다고 합시다. 처음에 인수 7은 if의 조건과 맞지 않기 때문에 else로 넘어가고 '7*factorial(6)'을 반환시킵니다. 반환된 값에 factorial 함수가 포함되어 있으므로 안에 있는 인수 6을 처리하고 이 과정이 계속 반복하다보면 반환된 값의 최종적인 모습은 '7*6*5*4*3*2*1*factorial(0)'과 같게 될 것입니다. 이때 인수 0을 받았을 경우 if의 조건에 따라 1이 반환되니 factorial(7)의 값은 '7*6*5*4*3*2*1'을 연산한 '5040'이 나오게됩니다. 다음 예시로는 피보나치 수열을 들어보았습니다.

피보나치 수열을 먼저 간략하게 설명하겠습니다. 어떤 사람이 아직 미 성숙한 새끼 토끼 한 쌍을 울타리 안에 가두어서 밖으로 빠져나가지 못하는 상황을 만들었습니다. 그리고 토끼 한 쌍은 한 달만에 성숙한 어른 토끼로 성장하여 매달에 한 번씩 암수 한쌍을 낳는다고 가정합니다. 그러면 가두고 나서 매달 토끼를 세어보면 "1, 1, 2, 3, 5, 8, 13, 21" 이런식으로 토끼가 늘어나게 됩니다. 여기서 패턴을 발견할 수 있는데 앞의 두 수의 합이 바로 뒤의 수가 되는 것을 확인할 수 있습니다. 그 예로 이 배열의 4항과 5항을 더하면 뒤의 6항의 값인 8과 같습니다.  

def Fibo(n):

    if n<1:

        return 0

    elif n==1 or n==2:

        return 1

    else:

        return Fibo(n-2) + Fibo(n-1)

위의 코드가 바로 피보나치 수열을 표현한 'Fibo' 함수로 인수받은 값에 해당하는 항의 숫자를 반환하는 함수입니다. 매개변수로 받은 인수는 if-elif-else 조건에 따라 나누게 되는데 0의 항은 없으므로 0을 반환하도록 if의 조건을 설정하였고 다음 elif 조건에서는 1과 2의 항은 모두 값이 1이므로 'or' 연산자로 설정하였습니다. else에서는 3항부터는 앞의 두 수를 합한 것이 뒤의 수라는 규칙을 이용하여서 'Fibo' 함수를 재귀호출 하였습니다. 만약 5를 인수로 받게된다면 'Fibo(3) + Fibo(4)'를 반환하게 될 것이고 다시 이 Fibo(3)과 Fibo(4)는 각각 'Fibo(1) + Fibo(2)'와 'Fibo(2) + Fibo(3)'으로 나뉘게 되서 연산하게 되어서 최종적으로 반환 값은 5가 되게됩니다.

지금까지 재귀함수와 파이썬으로 표현한 예시를 설명하였습니다. 재귀함수는 위에서 보았다시피 복잡한 작업을 간단한 작업으로 단순화시킬 수 있지만 메모리를 많이 잡아먹어서 속도가 느릴 수 있다는 단점이 존재합니다. 저도 공부하는 입장이라 아직은 큰 프로그램에 재귀함수를 사용하여 분석을 해보지 않았지만 무조건 좋다고 생각하여 재귀함수를 쓰면 부작용이 생길 것이므로 유의하여 사용해야할 것입니다. 이상으로 그럼 "파이썬 함수편2 - 재귀함수(팩토리얼, 피보나치 수열)" 포스팅을 마치도록 하겠습니다.