재귀하나의 함수 내에서 자신(해당 함수)을 다시 호출하여 작업을 수행하는 방식으로 문제를 푸는 방법이다. 재귀함수를 설계할 때 가장 중요한 점은 매 호출시마다 매개변수가 변한다는 점이다. 계속 다른 매개변수에 대해 같은 함수처리를 반복, 즉, 자기 자신을 계속 호출하는 것이다.

그러므로 탈출조건이 재귀에서는 매우 중요해진다. 자기 자신을 반복해서 부르는 행위를 언제 끝낼지 반드시 정의해주어야하는 것이다. 만약 매개변수가 변하지 않거나 특정 패턴만 반복하고 있다면 그 재귀함수는 영원히 실행을 반복하다가 스택오버플로우를 발생시킬 것이다. 따라서 재귀를 설계할 때는 반드시 탈출조건을 염두에 두어야 한다.


문제 1) 1부터 n까지 연속된 수의 합 출력

다음 문제는 매개변수로 정수를 받으며, 1부터 해당 정수까지의 모든 정수를 더하는 과정을 재귀로 푸는 문제이다.

문제 1. 수의 합 출력
1부터 N 까지 모든 수의 합을 출력하는 프로그램을 재귀함수로 구현
1. input 1부터 the number = 42 
    42까지의 합 : 903
2. input 1부터 the number = 1
    1까지의 합 : 1
3. input 1부터 the number = 468 
    468까지의 합 : 109746
4. input 1부터 the number = 1000 
    1000까지의 합 : 500500


코드 및 풀이

(1) while

재귀를 생각하기 전에 파이썬의 whilefor를 사용하여 해당 문제를 풀어보았다.

# while 사용

def seq_sum_while():
    result = 0
    n = input('input 1부터 the number = ')
    import copy
    num = copy.copy(n)
    n = int(n)
    while n != 0:
        result += n
        n = n - 1
    return '{n}까지의 합: {result}'.format(
        n=num, result=result)
   
### 실행 ###     
seq_sum_while(1000)

### 출력 ###
# input 1부터 the number = 10
# '10까지의 합: 55'

while문을 사용하여 푼 방법은 위과 같다. n이 0이 아닐 경우 계속해서 리턴값인 resultn을 더해주고 다음 반복문 실행 전에 n에서 1씩 빼준다.


(2) for

이번에는 for문을 사용해서 풀어보았다.

# for 사용

def seq_sum_for():
    result = 0
    n = int(input('input 1부터 the number = '))
    import copy
    num = copy.copy(n)
    for i in range(n + 1):
        result += i
    return '{n}까지의 합: {result}'.format(
        n=num, result=result)


### 실행 ###
seq_sum_for(1000)

### 출력 ###
# input 1부터 the number = 10
# '10까지의 합: 55'

for문은 훨씬 간단했다. n까지 포함해야하므로 range()함수를 사용하여 범위를 정해주고 반복문을 실행하면서 i를 리턴값인 result에 더해주었다.


(3) recursive function

다음은 재귀로 푼 방식이다.

def recursive01():
    import copy
    n = int(input("input 1에서부터 the number : "))
    num = copy.copy(n)
    def seq_sum_recursive(n):
        result = 0
        # 탈출조건
        if n <= 0:
            return result
        result = n + seq_sum_recursive(n - 1)
        return result
    print("{n}까지의 합: {result}".format(n=num, result=seq_sum_recursive(n)))
    
### 실행 ###
recursive01(1000)

### 출력 ###
# input 1에서부터 the number : 1000
# 1000까지의 합: 500500

n을 매개변수로 받았을 때, 자기자신을 계속 호출하면서 연속된 수를 더해나가야하므로 함수 자체를 연산식에 사용해야한다. 연속된 수를 매개변수 값에서부터 시작하여 1까지 더해나가려면 다음과 같은 식이 성립한다.

n + (n - 1) + (n - 2) + ... + 2 + 1
n + f(n - 1)

f(n - 1) = (n - 1) + f(n - 2)
f(n - 2) = (n - 2) + f(n - 3)
...
f(1) = 1 + f(0)
f(0) = 0 + f(-1)

그리고 탈출조건n이 1이 될 때까지 더해주어야 하므로 n == 0일 때 리턴값인 result를 반환하고 함수를 종료하도록 설계하였다.


실행시간 측정해보기

while, for, recursive로 푼 메서드의 실행시간을 각각 측정해보면 다음과 같다.

# n = 1000일 때 

# (1) while
runtime(seq_sum_while())   # 4.600151441991329e-07

# (2) for
runtime(seq_sum_for())   # 4.050089046359062e-07 

# (3) recursive
runtime(recursive01())   # 7.560010999441147e-07

더하기 연산 같은 간단한 알고리즘이지만 재귀가 확실히 느렸다. 또, 매개변수로 10000 정도의 값을 줄 경우 재귀를 사용한 메서드는 스택오버플로우를 발생시켰다.

함수의 실행시간 측정하는 방법은 따로 포스트할 예정이다.


완료 코드

# 완료 코드 

def add01():
    import copy
    n = int(input('input 1부터 the number = '))
    num = copy.copy(n)
    
    def seq_sum_while1(n):
        result = 0
        while n != 0:
            result += n
            n = n - 1
        return result

    def seq_sum_for1(n):
        result = 0
        for i in range(n + 1):
            result += i
        return result
        
    def seq_sum_recursive1(n):
        result = 0
        if n < 0:
            return result
        return n + seq_sum_recursive1(n - 1)
    
    print("while - {n}까지의 합: {result}".format(n=num, result=seq_sum_while1(n)))
    print("for - {n}까지의 합: {result}".format(n=num, result=seq_sum_for1(n)))
    print("recursive - {n}까지의 합: {result}".format(n=num, result=seq_sum_recursive1(n)))


### 실행 ###
add01()

### 출력 ###
# input 1부터 the number = 10
# while - 10까지의 합: 55
# for - 10까지의 합: 55
# recursive - 10까지의 합: 55


+추가

재귀를 사용한 메서드를 실행할 때 스택머신 가동 횟수를 제한하고 싶을 경우에는 재귀 횟수를 조절할 수 있는 내장 모듈을 사용한다.

import sys

# 1000 이상의 재귀 호출은 RecursionError를 발생시킨다.
sys.setrecursionlimit(1000)

먼저 선언해놓고 재귀를 사용한 메서드를 사용하면 된다.



Julia Hwang

디발자를 꿈꾸는 웹개발자의 블로그입니다.