[Python 기초] 프로그램의 입출력 - 재귀함수 호출

개요

재귀 함수(recursive function)란?

• 재귀함수란 어떤 함수를 정의할때 자신(함수)을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다.
• 다른 말로는 재귀호출, 되부름이라고 부르기도 하며 반복문 대신 재귀호출로 구현하는 것이 가능하다.
• 주의할 점 :
  • 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때 까지, 함수 호출 이후의 명령문이 수행되지 않는다. (다시 처음으로 돌아가기 때문)
  • 종료조건이 꼭 포함 되어야한다. (그렇지 않으면 무한루프에 들어간다)

예제 1 - 피보나치 수열 만들기

피보나치 수열은 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일때, 이후에 이어지는 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.

즉, 다음과 같은 수열이다.

0, 1, 1, 2, 3, 5, 8, 13, ...

여러가지의 방법이 있을 수 있지만 이럴때 재귀호출을 이용할 수 있다.

def fib(n):
    if n == 0: 
        return 0
    if n == 1:
        return 1
    return fib(n-2) + fib(n-1)

이러한 함수 정의는 다소 생소하다.

1. n이 0이면 0을 return
2. n이 1이면 1을 return
3. n이 2이면 fib(0) + fib(1)
4. n이 3이면 fib(1) + fib(2)
   …

이런식으로 마지막 줄에 처음에 정의했던 함수 fib(n)을 다시 호출하여 재귀적으로 구해나가는 것이다.

n = 5일 경우 순서를 직관적으로 이해해보면,

1. fib(5)입력
2. fib(3) + fib(4) fib()함수를 또 호출해서 다시 처음부터 계산을 수행하게 된다
3. fib(1) + fib(2) + fib(2) + fib(3)
4. 1 + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(2)
5. 1 + 0 + 1 + 0 + 1 + 1 + fib(0) + fib(1)
6. 4 + 0 + 1 = 5

fib(5)

[Output] 5

실제로 확인해봐도 답은 같다.

for i in range(10):
    print(fib(i))

[Output]
0
1
1
2
3
5
8
13
21
34

마지막으로 for문을 이용해서 피보나치 수열을 하나씩 출력해보았다.

예제 2 - 카운트다운 함수 만들기

카운트 다운의 시작 숫자를 입력하면 입력숫자를 기준으로 숫자가 하나씩 줄어들면서 폭탄이 터지는 함수를 만들어보자.

def countdown(n):
    if n == 0 :
        print("boom")
    else:
        print(n, end = " ")
        countdown(n-1)

위 예제와 같이 재귀호출을 사용했다.

마찬가지로 직관적으로 이해해 볼 수있다. 관련 블로그 설명중 이해가 쉬운 그림을 찾아 첨부한다.

출처 : https://gomguard.tistory.com/111

countdown(10)

[Output] 10 9 8 7 6 5 4 3 2 1 boom

countdown(10)을 입력하면 if문이 아닌 else문이 실행된다. 따라서 print()함수로 숫자가 출력되고 숫자를 하나 감소시켜 다시 정의한 countdown()함수를 재호출하게 된다. 결국 마지막에는 n이 0이 되면서 if문으로 재귀호출을 빠져나오게 된다.

이와 같이 재귀호출은 앞서 설명한 것처럼 2가지를 기억해야한다.

1. 재귀호출 전에 수행해야할 문장이 있다면 함수를 재호출하기 전에 입력해야 한다.
2. 재귀를 빠져나오게 되는 조건을 설정해 무한루프를 방지한다.(이 경우에는 n==0조건문으로 빠져 나왔다)

예제 3 - 팩토리얼(factiorial)

팩토리얼도 피보나치 수열과 마찬가지로 매우 일반적인 재귀함수라고 할 수 있다.
일반적으로 R에는 팩토리얼 함수를 제공하고 있다. 파이썬에는 있는지는 모르겠다.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n*factorial(n-1)

factorial(4)

[Output] 24

앞의 예제를 통해 학습했다면 어렵지 않게 만들 수 있다고 생각한다.
직관적으로 예를 들어 factorial(5)는 return n*factorial(n-1)을 통해 “5 곱하기 factorial(4)”가 되고 이는 다시 “5 곱하기 4 곱하기 factorial(3)”의 순서로 이어진다.

다시 한번 기억할만한 부분은 모든 예제에서 재귀를 빠져나가는 조건문이 존재한다는 것이다. (예를 들어 n이 0이 되거나 1이 되거나)

Reference

https://gomguard.tistory.com/111

도서 [점프 투 파이썬] 를 공부하며 작성하였습니다.