[파이썬 자료구조와 알고리즘] Chapter 10. 재귀호출

학습목표

• 재귀 호출의 개념과 작동 이해
• 재귀 호출을 위한 코드 형식 이해
• 재귀 호출을 다양한 응용 예로 연습

Section00. 생활 속 자료구조와 알고리즘

마트료시카 러시아인형

https://librewiki.net/wiki/%EB%A7%88%ED%8A%B8%EB%A3%8C%EC%8B%9C%EC%B9%B4

 

Section01. 재귀 호출의 기본

1. 재귀 호출의 개념

-재귀 호출(Recursion): 자신을 다시 호출하는 것

 

2. 재귀 호출의 작동

재귀 호출은 자신을 다시 호출하므로 강아지가 자신의 꼬리를 무고 빙글빙글 도는 형태임~

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

너무 많이 반복되면 자동종료됨

마지막 만나면 종료할 수 있도록 조건 추가 가능

def openBox():
	global count
    print("종이 상자를 엽니다")
    count-=1
    if count==0:
    	print("반지를 넣고 반환")
        return
    openBox()
    print("종이상자 닫음")
    
count=10
openBox()

아무리 많은 호출이더라도 마지막 호출에서 return을 만나게 되면 차근차근 원래 호출했던 곳으로 한 단계식 돌아감

 

 

Section02. 재귀 호출 작동 방식의 이해

1. 숫자 합계 내기

🤎반복문을 이용한 구현

1부터 10까지 합계 구하기

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

🤎재귀 함수를 이용한 구현

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

 

2. 팩토리얼 구하기

🤎반복문을 이용한 구현

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

🤎재귀 함수를 이용한 구현

def factorial(num):
	if num<=1:
    	return 1
    return num*factorial(num-1)
    
print('\n10!=', factorial(10))

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))

 

 

Section03. 재귀 호출의 연습

1. 우주선 발사 카운트다운

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

 

2. 별 모양 출력하기

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

 

3. 구구단 출력하기

def gugu(dan, num):
	print("%dX%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)

 

4. 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))

이건 다시보기

 

 

5. 배열의 합 계산하기

import random

def arySum(arr, n):
	if n<=0:
    	return arr[0]
    return arySum(arr, n-1)+arr[n]
    
arr=[random.randing(0, 255) for _ in range(random,randint(10, 20))]
#크기가 10~20개인 배열을 랜덤하게 생성하고, 0~255 사이의 숫자로 채움

print(ary)
print('배열 합계-->', arySum(ary, len(ary)-1))

6. 피보나치 수

def fivo(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=' ')

 

 

Section04. 재귀 호출의 응용

1. 회문 파단하기

-회문(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')

 

2. 프랙탈 그리기

-프랙탈(Fractal): 작은 조각이 전체와 비슷한 기하학적인 형태

'자기 유사성'(Self Similarity): 부분을 확대하면 전체와 동일한 또는 닮은 꼴의 모습을 나타내는 성질이 있음

 

간단한 원을 그리는 GUI 프로그래밍

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+4, cy+r, width=2, outline="red")

window.mianloop()

🤎원 도형의 간단한 프랙탈 그리기

하나의 원 안에 작은 원을 2개 좌우로 그리는 것을 재귀 호출로 반복하면 됨

3단계의 프랙탈 원 그리기

from tkinter import *

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

 

<연습문제>

1. 정답) 4

 

2. 정답) return 1

addNum(num-1)

 

3. num<=1

factorial(num-1)

num*retVal

 

4. n>0

('★'*n)

(n-1)

 

5. arySum(arr, n-1)+arr[n]

 

6. 0

1

n-1, n-2