[Python] 재귀 호출(Recursion)

재귀 호출(Recursion)

재귀 호출의 기본

재귀 호출의 개념

• 재귀 호출(Recursion) : 자기 자신을 다시 호출하는 것
• 재귀 호출은 처음 접하면 상당히 혼란스럽지만 자료구조와 알고리즘을 학습할 때 매우 유용한 방법이므로 꼭 알아두어야 한다.

 

재귀호출의 동작

• 파이썬에서는 재귀 호출이 너무 많아지면 반복을 자동 종료한다.

def openBox() :
    print("종이 상자를 엽니다.")
    openBox()

openBox()    # 처음 함수를 다시 호출

종이 상자를 엽니다.
종이 상자를 엽니다.
...
RecursionError: maximum recursion depth exceeded while pickling an object

 

• 반환 조건을 추가할 경우, 무한 반복에서 빠져나올 수 있다.

def openBox() :
    global count
    print("종이 상자를 엽니다.")
    # 반환 조건 추가
    count -= 1
    if count == 0 :
        print("무한 반복을 종료합니다.")
        return
    openBox()
    print("종이 상자를 닫습니다.")

count = 10
openBox()    # 처음 함수를 다시 호출

종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
종이 상자를 엽니다.
무한 반복을 종료합니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.
종이 상자를 닫습니다.

 

 

 

재귀 호출 동작 방식의 이해

① 숫자 합계 내기

• 1부터 10까지 합계를 내는 방법에는 반복문을 이용한 방법과 재귀 호출을 이용한 방법이 있다.

 

반복문을 이용한 구현

sumValue = 0
for n in range(10, 0, -1) :
    sumValue += n
print("10+9+…+1 =", sumValue)

10+9+…+1 = 55

 

재귀 함수를 이용한 구현

• 10+9+8+7+6+5+4+3+2+1 = 10 + (1부터 9까지 합계) = 10 + 9 + (1부터 8까지 합계)

 

def addNumber(num) :
    if num <= 1 :
        return 1
    return num + addNumber(num-1)

print(addNumber(10))

55

5부터 1까지 합계 재귀 호출

 

② 팩토리얼 구하기

• 팩토리얼(Factorial) : 특정 숫자부터 1까지 곱하는 것
• 10! = 10×9×8×7×6×5×4×3×2×1

 

반복문을 이용한 구현

factValue = 1    # 곱셈이므로 초깃값을 1로 설정
for n in range(10, 0, -1) :
    factValue *= n
print("10*9*…*1 =", factValue)

10*9*…*1 = 3628800

 

재귀 함수를 이용한 구현

def factorial(num) :
    if num <= 1 :
        return 1
    return num * factorial(num-1)

print('10! =', factorial(10))

10! = 3628800

 

5! 을 재귀 호출로 구현하기

def factorial(num) :
    if num <= 1 :
        print('1 반환')
        return 1
    print("%d * %d 호출" % (num, num-1))
    retVal = factorial(num-1)
    
    print("%d * %d!(=%d) 반환" % (num, num-1, retVal))
    return num * retVal

print('\n5! =', factorial(5))

5 * 4 호출
4 * 3 호출
3 * 2 호출
2 * 1 호출
1 반환
2 * 1!(=1) 반환
3 * 2!(=2) 반환
4 * 3!(=6) 반환
5 * 4!(=24) 반환

5! = 120

 

 

재귀 호출의 연습

① 우주선 발사 카운트 다운

def countDown(n) :
    if n == 0 :
        print('발사!')
    else :
        print(n)
        countDown(n-1)

countDown(5)

5
4
3
2
1
발사!

 

② 별 모양 출력하기

def printStar(n) :
    if n > 0 :
        printStar(n-1)
        print('★' * n)

printStar(5)

★
★★
★★★
★★★★
★★★★★

 

③ 구구단 출력하기

def gugu(dan, num) :
    print("%d x %d = %d" % (dan, num, dan*num))
    if num < 9 :
        gugu(dan, num+1)
    
for dan in range(2, 10) :
    print("## %d단 ##" % dan)
    gugu(dan, 1)

## 2단 ##
2 x 1 = 2
2 x 2 = 4
2 x 3 = 6
2 x 4 = 8
2 x 5 = 10
2 x 6 = 12
2 x 7 = 14
2 x 8 = 16
2 x 9 = 18
## 3단 ##
3 x 1 = 3
3 x 2 = 6
3 x 3 = 9
3 x 4 = 12
3 x 5 = 15
3 x 6 = 18
3 x 7 = 21
3 x 8 = 24
3 x 9 = 27
## 4단 ##
4 x 1 = 4
4 x 2 = 8
4 x 3 = 12
4 x 4 = 16
4 x 5 = 20
4 x 6 = 24
4 x 7 = 28
4 x 8 = 32
4 x 9 = 36
## 5단 ##
5 x 1 = 5
5 x 2 = 10
5 x 3 = 15
5 x 4 = 20
5 x 5 = 25
5 x 6 = 30
5 x 7 = 35
5 x 8 = 40
5 x 9 = 45
## 6단 ##
6 x 1 = 6
6 x 2 = 12
6 x 3 = 18
6 x 4 = 24
6 x 5 = 30
6 x 6 = 36
6 x 7 = 42
6 x 8 = 48
6 x 9 = 54
## 7단 ##
7 x 1 = 7
7 x 2 = 14
7 x 3 = 21
7 x 4 = 28
7 x 5 = 35
7 x 6 = 42
7 x 7 = 49
7 x 8 = 56
7 x 9 = 63
## 8단 ##
8 x 1 = 8
8 x 2 = 16
8 x 3 = 24
8 x 4 = 32
8 x 5 = 40
8 x 6 = 48
8 x 7 = 56
8 x 8 = 64
8 x 9 = 72
## 9단 ##
9 x 1 = 9
9 x 2 = 18
9 x 3 = 27
9 x 4 = 36
9 x 5 = 45
9 x 6 = 54
9 x 7 = 63
9 x 8 = 72
9 x 9 = 81

 

 

④ N제곱 계산하기

tab = ''
def pow(x, n) :
    global tab
    tab += ' '
    if n == 0 :
        return 1
    print(tab + "%d*%d^(%d-%d)" % (x, x, n, 1))
    return x * pow(x, n-1)

print('2^4')
print('답 -->', pow(2, 4))

2^4
 2*2^(4-1)
  2*2^(3-1)
   2*2^(2-1)
    2*2^(1-1)
답 --> 16

 

⑤ 배열의 합 계산하기

import random

def arySum(arr, n) :
    if n <= 0 :
        return arr[0]
    return arySum(arr, n-1) + arr[n]

ary = [random.randint(0, 255) for _ in range(random.randint(10, 20))]
print(ary)
print('배열 합계 -->', arySum(ary, len(ary)-1))

[67, 195, 150, 95, 53, 52, 39, 20, 31, 105, 255, 147]
배열 합계 --> 1209

 

⑥ 피보나치 수

• 피보나치 수(Fibonacci Numbers) : 첫 번째는 0, 두 번째는 1이며, 그 이후는 앞 두 숫자의 합계인 수열
  • 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

def fibo(n) :
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        return fibo(n-1) + fibo(n-2)

print('피보나치 수 --> 0 1 ', end=' ')
for i in range(2, 20) :
    print(fibo(i), end=' ')

피보나치 수 --> 0 1  1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

 

 

재귀 호출의 응용

① 회문(Palindrome) 판단하기

• 회문(Palindrome) : 앞에서부터 읽든 뒤에서부터 읽든 동일한 단어나 문장
• 대·소문자는 구분하지 않고, 공백이나 특수 문자는 제외한다.
• 첫 글자와 마지막 글자를 비교하여 같으면 회문일 수 있고, 다르면 회문이 아니다.
• 비교하지 않은 글자가 한 글자 이하이면 회문으로 확정하고, 한 글자 이하가 아니면 첫 글자는 다음 글자로 마지막 글자는 바로 앞 글자로 이동하는 식으로 비교하고 확인하는 과정을 반복한다.

회문인 예	회문이 아닌 예

 

구현

def palindrome(pStr) :
    if len(pStr) <= 1 :
        return True

    if pStr[0] != pStr[-1] :
        return False

    return palindrome(pStr[1:len(pStr)-1])

strAry = ["reaver", "kayak", "Borrow or rob", "주유소의 소유주", "야 너 이번주 주번이 너야", "살금 살금"]

for testStr in strAry :
    print(testStr, end = '--> ' )
    testStr = testStr.lower().replace(' ','')
    if palindrome(testStr) :
        print('O')
    else :
        print('X')

reaver--> X
kayak--> O
Borrow or rob--> O
주유소의 소유주--> O
야 너 이번주 주번이 너야--> O
살금 살금--> X

 

② 프랙탈 그리기

• 프랙탈(Fractal) : 작은 조각이 전체와 비슷한 기하학적인 형태를 의미하며, 이런 특징을 '자기 유사성'이라고 한다.
  
  • 자기 유사성(Self Similarity) : 부분을 확대하면 전체와 동일한 또는 닮은 꼴의 모습을 나타내는 성질
• 프랙탈은 자연 현상에서도 많이 볼 수 있다.
  • 나무줄기, 번개, 강줄기, 나뭇잎, 산호초 등
• 프랙탈은 자연뿐 아니라 수하적 도형으로도 구성할 수 있다.
• 도형을 그릴 때는 GUI(Graphical User Interface) 형식의 화면 출력이 필요하다.
  • 파이썬은 tkinter 라는 간단한 라이브러리를 제공해서 윈도 창을 간단히 만들고 점, 선, 원 등을 그리는 방법을 제공한다.

 

구현 : 간단한 원 그리기

from tkinter import *

window = Tk()
canvas = Canvas(window, height=1000, width=1000, bg='white')
canvas.pack()

cx = 1000 // 2
cy = 1000 // 2
r = 400
canvas.create_oval(cx-r, cy-r, cx+r, cy+r, width=2, outline="red")

window.mainloop()

 

구현 : 원 도형의 간단한 프랙탈 그리기

from tkinter import *

def drawCircle(x, y, r) :
    global count
    count += 1
    canvas.create_oval(x-r, y-r, x+r, y+r)
    canvas.create_text(x, y-r, text=str(count), font=('', 30))
    if r >= radius/2 :
        drawCircle(x-r//2, y, r//2)
        drawCircle(x+r//2, y, r//2)

count = 0
wSize = 1000
radius = 400

window = Tk()
canvas = Canvas(window, height=wSize, width=wSize, bg='white')

drawCircle(wSize//2, wSize//2, radius)

canvas.pack()
window.mainloop()

 

구현 : 전체 프랙탈 원 그리기

from tkinter import *
import random

def drawCircle(x, y, r) :
    canvas.create_oval(x-r, y-r, x+r, y+r, width=2, outline=random.choice(colors))
    if r >= 5 :
        drawCircle(x+r//2, y, r//2)
        drawCircle(x-r//2, y, r//2)

colors = ["red", "green", "blue", "black", "orange", "indigo", "violet"]
wSize = 1000
radius = 400

window = Tk()
window.title("원 모양의 프랙탈")
canvas = Canvas(window, height=wSize, width=wSize, bg='white')

drawCircle(wSize//2, wSize//2, radius)

canvas.pack()
window.mainloop()