Chapter 10 - 재귀 호출 (Recursion)

Chapter 10

재귀 호출

Recursion

Part 1  재귀 호출의 기본과 이해 · Recursion Basics & Understanding
Part 2  재귀 호출의 다양한 연습 · Recursion Practice
Part 3  재귀 호출의 응용 · Recursion Applications

01

Part 1

재귀 호출의 기본과 이해

Recursion Basics & Understanding

재귀 호출의 개념, 무한 재귀와 종료 조건, 숫자 합계와 팩토리얼을 학습합니다.

생활 속 재귀 구조

Recursion in Daily Life

한국어

재귀란 무엇인가?

재귀(Recursion)란 자기 자신을 다시 호출하는 것입니다. 동일한 작동을 반복하는 알고리즘을 재귀 알고리즘이라 합니다.

거울 속의 거울

양쪽에 거울이 있을 때 거울에 비친 자신이 무한 반복해서 비치는 현상 — 이것이 바로 재귀입니다!

마트료시카 인형

인형 안에 같은 모양의 작은 인형이 계속 들어 있는 러시아 전통 인형입니다. 열 때마다 같은 동작을 반복합니다.

핵심 비유

종이 상자를 겹겹이 열어서 마지막 상자에 반지를 넣고, 다시 역순으로 상자를 닫는 과정이 바로 재귀 호출입니다!

English

What is Recursion?

Recursion means a function calling itself. An algorithm that repeats the same operation is called a recursive algorithm.

Mirror in a Mirror

When two mirrors face each other, the reflection repeats infinitely — that's recursion!

Matryoshka Dolls

Russian nesting dolls: each doll contains a smaller version of itself. Opening each one is the same action repeated.

Box Analogy

Open nested boxes one by one until you find the ring in the innermost box, then close them back in reverse order. This is exactly how recursion works!

Key Insight

Recursion has two phases:
Going deeper (opening boxes) → function calls itself
Coming back (closing boxes) → function returns

무한 재귀와 종료 조건

Infinite Recursion & Base Case

한국어

무한 재귀 (Code10-01)

def openBox():
    print("종이 상자를 엽니다. ^^")
    openBox()  # 자기 자신 호출!

openBox()  # 처음 호출

문제점!

종료 조건이 없어 무한 반복됩니다. 실행하면 RecursionError가 발생합니다.

종료 조건 추가 (Code10-02)

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

count = 10
openBox()

return의 역할

return을 만나면 자신을 호출한 곳으로 되돌아갑니다. 열었던 상자를 역순으로 닫는 과정입니다!

English

Infinite Recursion (Code10-01)

The Problem

openBox() calls itself with no stopping condition → infinite loop → RecursionError!

Adding a Base Case (Code10-02)

How It Works

1. count = 10 → open 10 boxes
2. Each call decrements count
3. When count == 0 → return (base case!)
4. After return, execute remaining code: "close box"

Every Recursion Needs

Base case: the condition that stops recursion (here: count == 0)
Recursive case: the function calling itself
Without a base case → infinite recursion → crash!

숫자 합계와 팩토리얼

Sum of Numbers & Factorial

한국어

1~N 합계 (Code10-03)

1부터 N까지의 합을 재귀로 구합니다.

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

print(addNumber(10))  # 55

핵addNumber(10) = 10 + addNumber(9) = 10 + 9 + addNumber(8) = ... = 10+9+8+...+1 = 55

팩토리얼 N! (Code10-04)

N! = N × (N-1) × ... × 1

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

print('5! =', factorial(5))
# 5! = 120

English

Sum 1~N (Code10-03)

Pattern

addNumber(n) = n + addNumber(n-1)
Base case: n ≤ 1 → return 1
This replaces a for loop with recursion!

Factorial N! (Code10-04)

Pattern

factorial(n) = n × factorial(n-1)
Base case: n ≤ 1 → return 1
5! = 5×4×3×2×1 = 120

Loop vs Recursion

Loop: result = 1; for i in range(1,n+1): result *= i
Recursion: return n * factorial(n-1)
Both give the same answer, but recursion is more elegant for problems that are naturally self-similar!

The Two Ingredients

Every recursive function needs:
1. Base case: when to stop
2. Recursive case: calling itself with a smaller problem

팩토리얼 단계별 동작

Factorial Step-by-Step

한국어

5! 재귀 호출 과정

Code10-04의 상세 실행 과정입니다.

English

5! Step-by-Step Execution

1factorial(5) → 5 * factorial(4) — need factorial(4) first!

2factorial(4) → 4 * factorial(3) — need factorial(3)!

3factorial(3) → 3 * factorial(2) — need factorial(2)!

4factorial(2) → 2 * factorial(1) — need factorial(1)!

5factorial(1) → return 1 (base case reached!)

Unwinding Phase

factorial(1) = 1
factorial(2) = 2 × 1 = 2
factorial(3) = 3 × 2 = 6
factorial(4) = 4 × 6 = 24
factorial(5) = 5 × 24 = 120

Two Phases of Recursion

Winding: calls stack up, going deeper
Unwinding: results return back up the chain
Like opening boxes, then closing them in reverse!

연습문제 Part 1

Practice Part 1

한국어

연습문제 1-1 : 상자 열기/닫기 (Code10-02)

10개의 종이 상자를 재귀적으로 열고, 마지막 상자에서 반지를 넣은 후, 역순으로 상자를 닫는 프로그램을 작성하시오.

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

count = 10
openBox()

연습문제 1-2 : 범위 합계 (Self10-01)

두 숫자를 입력받아, 작은 수부터 큰 수까지의 합계를 재귀 함수로 구하시오. 예: 3, 7 → 3+4+5+6+7 = 25

def addNumber(num1, num2):
    if num2 <= num1:
        return num1
    return num2 + addNumber(num1, num2 - 1)

num1 = int(input('숫자1-->'))
num2 = int(input('숫자2-->'))
if num1 > num2:
    num1, num2 = num2, num1
print(addNumber(num1, num2))

English

Practice 1-1 : Open/Close Boxes (Code10-02)

Write a program that recursively opens 10 boxes, places a ring in the last box, then closes boxes in reverse order.

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

count = 10
openBox()

Practice 1-2 : Range Sum (Self10-01)

Input two numbers and compute the sum from smaller to larger using recursion. E.g., 3, 7 → 3+4+5+6+7 = 25

def addNumber(num1, num2):
    if num2 <= num1:
        return num1
    return num2 + addNumber(num1, num2 - 1)

num1 = int(input('숫자1-->'))
num2 = int(input('숫자2-->'))
if num1 > num2:
    num1, num2 = num2, num1
print(addNumber(num1, num2))

02

Part 2

재귀 호출의 다양한 연습

Recursion Practice

카운트다운, 별 출력, 구구단, N제곱, 배열 합계, 피보나치 수열을 재귀로 구현합니다.

카운트다운 & 별 출력

Countdown & Star Pattern

한국어

카운트다운 (Code10-05)

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

countDown(5)

출력

5 → 4 → 3 → 2 → 1 → 발사!!

별 출력 (Code10-06)

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

printStar(5)

출력

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

English

Countdown (Code10-05)

Pattern: Action Before Recursion

Print before the recursive call → numbers print in descending order (5,4,3,2,1).
Base case: n == 0 → print "Launch!!"

Star Pattern (Code10-06)

Pattern: Action After Recursion

Print after the recursive call → stars print in ascending order (1,2,3,4,5)!
printStar(n-1) is called first, then print('★'*n).

Before vs After

Print before recursion → descending (top-down)
Print after recursion → ascending (bottom-up)
This is the power of recursion: the order of operations around the recursive call determines output order!

구구단 & N제곱

Multiplication Table & Power

한국어

구구단 출력 (Code10-07)

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)

작동 원리

gugu(2, 1) → 2×1 출력 후 gugu(2, 2) 호출 → ... → gugu(2, 9)에서 9 < 9 거짓이므로 종료

N제곱 (Code10-08)

def pow(x, n):
    if n == 0:
        return 1
    return x * pow(x, n-1)

print('답 -->', pow(2, 4))
# 답 --> 16

핵2⁴ = 2 × 2³ = 2 × 2 × 2² = 2 × 2 × 2 × 2¹ = 2 × 2 × 2 × 2 × 2⁰ = 16

English

Multiplication Table (Code10-07)

Two Parameters

gugu(dan, num) — dan is fixed for each table, num increments from 1 to 9 via recursion.
The outer for loop handles switching between tables (2단~9단).

Power x^n (Code10-08)

Pattern

pow(x, n) = x × pow(x, n-1)
Base case: n == 0 → return 1
(anything to the power of 0 is 1)

Execution: pow(2, 4)

pow(2,4) = 2 × pow(2,3)
pow(2,3) = 2 × pow(2,2)
pow(2,2) = 2 × pow(2,1)
pow(2,1) = 2 × pow(2,0)
pow(2,0) = 1 (base case)
→ 2×2×2×2×1 = 16

배열 합계 & 피보나치

Array Sum & Fibonacci

한국어

배열 합계 (Code10-09)

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

피보나치 수열 (Code10-10)

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

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

English

Array Sum (Code10-09)

Pattern

arySum(arr, n) = arySum(arr, n-1) + arr[n]
Base case: n ≤ 0 → return arr[0]
Recursively sums from index 0 to n!

Fibonacci (Code10-10)

Fibonacci Formula

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) for n ≥ 2
Each number is the sum of the two preceding ones.

Double Recursion!

Fibonacci calls itself twice per call: fibo(n-1) + fibo(n-2). This creates a tree of calls that grows exponentially — very slow for large n!

Output

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

연습문제 Part 2

Practice Part 2

한국어

연습문제 2-1 : 팩토리얼 (Code10-04)

재귀 함수로 N!을 구하고, 호출/반환 과정을 출력하시오. 입력: 5 → 출력: 5! = 120

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

연습문제 2-2 : 가로 구구단 (Self10-02)

구구단을 가로로 출력하시오. 각 행에 2×1=2 3×1=3 ... 9×1=9 형태로 출력합니다.

def gugu(dan, num):
    print("%dx%d=%2d"
          % (dan, num, dan*num), end='  ')
    if dan < 9:
        gugu(dan+1, num)

for num in range(1, 10):
    gugu(2, num)
    print()

English

Practice 2-1 : Factorial (Code10-04)

Implement N! with recursion, printing call/return process. Input: 5 → Output: 5! = 120

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

Practice 2-2 : Horizontal Gugu (Self10-02)

Print multiplication table horizontally. Each row: 2×1=2 3×1=3 ... 9×1=9

def gugu(dan, num):
    print("%dx%d=%2d"
          % (dan, num, dan*num), end='  ')
    if dan < 9:
        gugu(dan+1, num)

for num in range(1, 10):
    gugu(2, num)
    print()

03

Part 3

재귀 호출의 응용

Recursion Applications

회문 판단, 프랙탈 그래픽, 진수 변환, 시에르핀스키 삼각형 등 재귀의 실전 응용을 학습합니다.

회문(팰린드롬) 판단

Palindrome Check

한국어

회문이란?

회문(Palindrome)이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열입니다. 예: "kayak", "주유소의 소유주"

        재귀적 판단 원리

        ① 문자열 길이가 1 이하 → True (회문)

        ② 첫 글자 ≠ 끝 글자 → False (회문 아님)

        ③ 첫·끝을 제거하고 나머지로 재귀 호출

Code10-11 : 회문 판단

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

핵심 포인트: 공백 제거(.replace(' ',''))와 소문자 변환(.lower())으로 전처리 후 비교합니다. 슬라이싱 pStr[1:len(pStr)-1]로 양끝을 제거합니다.

English

What is a Palindrome?

A Palindrome is a string that reads the same forwards and backwards. E.g., "kayak", "racecar"

        Recursive Logic

        ① String length ≤ 1 → True (palindrome)

        ② First char ≠ Last char → False (not palindrome)

        ③ Strip first & last, recurse on the rest

Code10-11 : Palindrome Check

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

Key Point: Preprocess with .replace(' ','') (remove spaces) and .lower() (lowercase) before comparison. Slicing pStr[1:len(pStr)-1] strips both ends.

프랙탈 — 재귀 원 그리기

Fractal — Recursive Circles

한국어

프랙탈이란?

프랙탈(Fractal)은 일부를 확대하면 전체와 같은 모양이 반복되는 구조입니다. 재귀 호출로 자연스럽게 구현할 수 있습니다.

        Code10-13 작동 원리

        ① 중심 (x, y)에 반지름 r인 원을 그림

        ② r ≥ radius/2이면 → 왼쪽·오른쪽 자식 원 재귀

        ③ 자식 원: 반지름 r//2, 좌측 (x−r//2, y), 우측 (x+r//2, y)

Code10-13 : 프랙탈 원 (번호 표시)

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

종료 조건: r < radius//2이면 더 이상 재귀하지 않습니다. 원이 너무 작아지면 멈추는 것이 핵심입니다.

English

What is a Fractal?

A Fractal is a structure where zooming into any part reveals the same repeating pattern as the whole. It maps naturally to recursion.

        Code10-13 Logic

        ① Draw circle at center (x, y) with radius r

        ② If r ≥ radius/2 → recurse left & right child circles

        ③ Children: radius r//2, left (x−r//2, y), right (x+r//2, y)

Code10-13 : Fractal Circles (Numbered)

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

Base Case: When r < radius//2, stop recursing. The key is stopping when circles get too small.

진수 변환 — 재귀 나눗셈

Base Conversion — Recursive Division

한국어

10진수 → 2/8/16진수 변환

10진수를 다른 진수로 변환할 때 "나누고 나머지를 역순으로 출력"하는 원리를 재귀로 구현합니다.

        재귀 변환 원리 (예: 13 → 2진수)

        notation(2, 13): 13 ÷ 2 = 몫 6, 나머지 1

          notation(2, 6): 6 ÷ 2 = 몫 3, 나머지 0

            notation(2, 3): 3 ÷ 2 = 몫 1, 나머지 1

              notation(2, 1): 1 < 2 → 출력 1

              → 결과: 1 1 0 1

Ex10-01 : 진수 변환

def notation(base, n):
    if n < base:
        print(numberChar[n], end=' ')
    else:
        notation(base, n // base)
        print(numberChar[n % base], end=' ')

numberChar = ['0','1','2','3','4',
  '5','6','7','8','9']
numberChar += ['A','B','C','D','E','F']

number = int(input('10진수 입력 -->'))
print('\n 2진수 : ', end=' ')
notation(2, number)
print('\n 8진수 : ', end=' ')
notation(8, number)
print('\n16진수 : ', end=' ')
notation(16, number)

핵심: 재귀 호출 후에 나머지를 출력하므로 역순이 됩니다. n < base일 때가 종료 조건입니다.

English

Decimal → Binary/Octal/Hex

Converting decimal to another base uses the principle: "divide and print remainders in reverse order", implemented recursively.

        Recursive Conversion (e.g., 13 → binary)

        notation(2, 13): 13 ÷ 2 = quotient 6, remainder 1

          notation(2, 6): 6 ÷ 2 = quotient 3, remainder 0

            notation(2, 3): 3 ÷ 2 = quotient 1, remainder 1

              notation(2, 1): 1 < 2 → print 1

              → Result: 1 1 0 1

Ex10-01 : Base Conversion

def notation(base, n):
    if n < base:
        print(numberChar[n], end=' ')
    else:
        notation(base, n // base)
        print(numberChar[n % base], end=' ')

numberChar = ['0','1','2','3','4',
  '5','6','7','8','9']
numberChar += ['A','B','C','D','E','F']

number = int(input('Enter decimal -->'))
print('\n Binary : ', end=' ')
notation(2, number)
print('\n Octal  : ', end=' ')
notation(8, number)
print('\n   Hex  : ', end=' ')
notation(16, number)

Key: The remainder is printed after the recursive call, producing the reverse order. n < base is the base case.

시에르핀스키 삼각형

Sierpinski Triangle

한국어

시에르핀스키 삼각형이란?

시에르핀스키 삼각형은 정삼각형을 4개의 작은 삼각형으로 나누고, 가운데 삼각형을 제거한 뒤 나머지 3개에 대해 같은 과정을 반복하는 프랙탈입니다.

        재귀 분할 원리

        ① size ≥ 30이면 → 3개의 작은 삼각형으로 재귀 분할

          · 좌하단 (x, y, size/2)

          · 우하단 (x+size/2, y, size/2)

          · 상단 (x+size/4, y−size×√3/4, size/2)

        ② size < 30이면 → 빨간 삼각형을 직접 그림 (종료 조건)

Ex10-02 : 시에르핀스키 삼각형

from tkinter import *

def drawTriangle(x, y, size):
    if size >= 30:
        drawTriangle(x, y, size/2)
        drawTriangle(x+size/2, y, size/2)
        drawTriangle(x+size/4,
            int(y-size*(3**0.5)/4),
            size/2)
    else:
        canvas.create_polygon(
            x, y, x+size, y,
            x+size/2,
            y-size*(3**0.5)/2,
            fill='red', outline="red")

wSize = 1000
window = Tk()
window.title("삼각형 모양의 프랙탈")
canvas = Canvas(window,
    height=wSize, width=wSize, bg='white')
drawTriangle(wSize/5, wSize/5*4,
    wSize*2/3)
canvas.pack(); window.mainloop()

핵심: 3중 재귀 호출(좌하단, 우하단, 상단)이 이진 트리가 아닌 3진 트리 형태의 재귀입니다. size < 30에서 실제 삼각형을 그립니다.

English

What is a Sierpinski Triangle?

The Sierpinski Triangle is a fractal formed by dividing an equilateral triangle into 4 smaller triangles, removing the center one, and repeating for the remaining 3.

        Recursive Division Logic

        ① If size ≥ 30 → recursively divide into 3 sub-triangles:

          · Bottom-left (x, y, size/2)

          · Bottom-right (x+size/2, y, size/2)

          · Top (x+size/4, y−size×√3/4, size/2)

        ② If size < 30 → draw a red triangle directly (base case)

Ex10-02 : Sierpinski Triangle

from tkinter import *

def drawTriangle(x, y, size):
    if size >= 30:
        drawTriangle(x, y, size/2)
        drawTriangle(x+size/2, y, size/2)
        drawTriangle(x+size/4,
            int(y-size*(3**0.5)/4),
            size/2)
    else:
        canvas.create_polygon(
            x, y, x+size, y,
            x+size/2,
            y-size*(3**0.5)/2,
            fill='red', outline="red")

wSize = 1000
window = Tk()
window.title("Sierpinski Triangle Fractal")
canvas = Canvas(window,
    height=wSize, width=wSize, bg='white')
drawTriangle(wSize/5, wSize/5*4,
    wSize*2/3)
canvas.pack(); window.mainloop()

Key: Triple recursion (bottom-left, bottom-right, top) forms a ternary tree, not binary. Actual triangles are drawn only when size < 30.

연습문제 Part 3

Practice Part 3

한국어

연습 3-1 : 진수 변환 (Ex10-01)

10진수를 입력받아 2진수, 8진수, 16진수로 변환하는 재귀 함수 notation(base, n)을 작성하시오. 16진수에서는 A~F를 사용합니다.

def notation(base, n):
    if n < base:
        print(numberChar[n], end=' ')
    else:
        notation(base, n // base)
        print(numberChar[n % base], end=' ')

numberChar = ['0','1','2','3','4',
  '5','6','7','8','9']
numberChar += ['A','B','C','D','E','F']

number = int(input('10진수 입력 -->'))
print('\n 2진수 : ', end=' ')
notation(2, number)
print('\n 8진수 : ', end=' ')
notation(8, number)
print('\n16진수 : ', end=' ')
notation(16, number)

연습 3-2 : 시에르핀스키 삼각형 (Ex10-02)

tkinter를 사용하여 시에르핀스키 삼각형 프랙탈을 재귀적으로 그리는 프로그램을 작성하시오. size가 30 미만이면 빨간색 삼각형을 그립니다.

from tkinter import *

def drawTriangle(x, y, size):
    if size >= 30:
        drawTriangle(x, y, size/2)
        drawTriangle(x+size/2, y, size/2)
        drawTriangle(x+size/4,
            int(y-size*(3**0.5)/4),
            size/2)
    else:
        canvas.create_polygon(
            x, y, x+size, y,
            x+size/2,
            y-size*(3**0.5)/2,
            fill='red', outline="red")

wSize = 1000
window = Tk()
window.title("삼각형 모양의 프랙탈")
canvas = Canvas(window,
    height=wSize, width=wSize, bg='white')
drawTriangle(wSize/5, wSize/5*4,
    wSize*2/3)
canvas.pack(); window.mainloop()

English

Practice 3-1 : Base Conversion (Ex10-01)

Write a recursive function notation(base, n) that converts a decimal number to binary, octal, and hexadecimal. Use A~F for hex digits.

def notation(base, n):
    if n < base:
        print(numberChar[n], end=' ')
    else:
        notation(base, n // base)
        print(numberChar[n % base], end=' ')

numberChar = ['0','1','2','3','4',
  '5','6','7','8','9']
numberChar += ['A','B','C','D','E','F']

number = int(input('Enter decimal -->'))
print('\n Binary : ', end=' ')
notation(2, number)
print('\n Octal  : ', end=' ')
notation(8, number)
print('\n   Hex  : ', end=' ')
notation(16, number)

Practice 3-2 : Sierpinski Triangle (Ex10-02)

Write a program using tkinter to recursively draw a Sierpinski triangle fractal. Draw red triangles when size is less than 30.

from tkinter import *

def drawTriangle(x, y, size):
    if size >= 30:
        drawTriangle(x, y, size/2)
        drawTriangle(x+size/2, y, size/2)
        drawTriangle(x+size/4,
            int(y-size*(3**0.5)/4),
            size/2)
    else:
        canvas.create_polygon(
            x, y, x+size, y,
            x+size/2,
            y-size*(3**0.5)/2,
            fill='red', outline="red")

wSize = 1000
window = Tk()
window.title("Sierpinski Triangle Fractal")
canvas = Canvas(window,
    height=wSize, width=wSize, bg='white')
drawTriangle(wSize/5, wSize/5*4,
    wSize*2/3)
canvas.pack(); window.mainloop()