재귀 호출

• 재귀 호출: 함수가 자기 자신을 다시 호출하는 기법
• 기저 사례: 재귀 호출을 멈추는 조건
• 재귀 사례: 함수가 자기 자신을 호출하여 문제를 더 작은 하위 문제로 분할하는 부분
• 장점: 간결성, 문제 분할
• 단점: 성능 문제, 중복 계산

#재귀 호출의 작동
def openBox() :
    print('종이 상자를 엽니다. ^^')
    openBox()

openBox()

종이 상자를 엽니다. ^^
종이 상자를 엽니다. ^^
...
종이 상자를 엽니다. ^^
종이 상자를 엽니다. ^^
종이 상자를 엽니다. ^^

 

#재귀 호출 함수(반환 조건 추가)
def openBox() :
    global count
    print('종이 상자를 엽니다. ^^')
    count -= 1
    if count == 0 :
        print('반지를 넣고 반환합니다.')
        return
    openBox()
    print('종이 상자를 닫습니다. ^^')
    
count = 5
openBox()

종이 상자를 엽니다. ^^
종이 상자를 엽니다. ^^
종이 상자를 엽니다. ^^
종이 상자를 엽니다. ^^
종이 상자를 엽니다. ^^
반지를 넣고 반환합니다.
종이 상자를 닫습니다. ^^
종이 상자를 닫습니다. ^^
종이 상자를 닫습니다. ^^
종이 상자를 닫습니다. ^^

 

#재귀 호출 이해
def addNumber(num) :
    if num <= 1 :
        return 1
    return num + addNumber(num - 1)

print(addNumber(10))

55

 

#재귀 호출 이해 : 팩토리얼 구하기
def factorial(num) :
    if num <= 1 :
        return 1
    return num * factorial(num - 1)

print(factorial(5))

120

 

#재귀 호출 연습 : 우주선 발사 카운트 다운
def countDown(n) :
    if n == 0 :
        print('발사')
    else :
        print(n)
        countDown(n - 1)

countDown(5)

5
4
3
2
1
발사

 

#재귀 호출 연습 : 별 찍기
def printStars(n) :
    if n > 0 :
        printStars(n - 1)
        print('*' * n)

printStars(5)

*
**
***
****
*****

 

#재귀 호출 연습 : 구구단
def gugu(dan, num) :
    print('%d * %d = %d' % (dan, num, dan * num))
    if num < 9 :
        gugu(dan, num + 1)

gugu(2, 1)

2 * 1 = 2
2 * 2 = 4
2 * 3 = 6
2 * 4 = 8
2 * 5 = 10
2 * 6 = 12
2 * 7 = 14
2 * 8 = 16
2 * 9 = 18

 

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

[65, 101, 76, 24, 200, 28, 7, 92, 255, 233]
배열 합계 --> 1081
Selection deleted

 

#피보나치 수
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