초보몽키의 개발공부로그

강의노트 15-1. 재귀함수(피보나치, 하노이의 탑, 최소공배수 등)

15 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

재귀함수 (recursion)

  • 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 부른다.
  • 반드시 탈출조건이 있어야 stack overflow를 방지할 수 있다.
  • 같은 행위가 반복될 때 재귀함수를 사용한다.

예시 - 순차탐색

def search(li, begin, end, target):
    if begin>end:
        return -1
    elif target == li[begin]:
        return begin
    else:
        return search(li, begin+1, end, target)

li = [1,6,10,7,2,5]
target = 10
search(li, 0, 5, 10) # 2

예시 - 2진수 변환

def print_binary(n):
    if n<2:
        print(n, end='')
    else:
        print_binary(n//2)
        print(n%2,end='')

print_binary(15) #1111

예시 - 배열의 합

  • li[0]에서 li[n-1] 까지의 합을 구하여 리턴
  • 재귀적 사고방식: li[n-1] + (li[n-2] 까지의 합) 을 구한다
def sum(n, li):
    if n<=0 or n >= len(li):
        return 0
    return li[n-1] + sum(n-1, li)

예시 - 0~n 까지의 합계 구하기

def sum(n): # 이 함수의 목표는 0~n 까지의 합을 구하는 것이다
    if n == 0: # n=0 이면 합은 0이다
        return 0
    return n + sum(n-1) # n이 0보다 크면 0에서 n 까지의 합은, n-1까지의 합에 n을 더한 것이다.

sum(4) # 10
views

예시 - 1~n 까지의 곱 구하기

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

factorial(4)
views

예시 - x^n 구현

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

power(2,10) # 1024

예시 - 피보나치 수열

# 피보나치 수열의 index n의 값을 리턴
# 피보나치 수열 : 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
def fibo(n):
    # 재귀함수는 탈출조건이 꼭 필요하다.
    if n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

# index n까지의 피보나치 수열 구하기
def fibo_list(n):
    for i in range(n):
        print(fibo(i), end= " ")

예시 - 최대공약수 (유클리드 호제법)

  • 참고: 두수의 곱을 최대공약수로 나누면 최소공배수가된다.
def gcd(m, n):
    if m < n:
        m, n = n, m
    if m % n == 0:
        return n
    else:
        return gcd(n, m%n)

print(gcd(48, 60)) # 12

예시 - 하노이 타워

  • 참고
  • A에 있는 n개의 원반 중 맨 아래에 있는 n번째 원반을 제외한 나머지 원반을 모두 B로 옮긴다.
  • A에 남은 하나의 원반을 C로 옮긴다.
  • B의 모든 원반을 C로 옮긴다.
def hanoi(num, _from, _by, _to):
    #탈출 조건
    if num == 1:
        print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num))
        return

    hanoi(num-1, _from, _to, _by)
    print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num))
    hanoi(num-1, _by, _from, _to)

if __name__ == "__main__":
    while 1:
        numOfTray = int(input("원반의 개수를 입력하세요!(종료 : 0) :"))
        if numOfTray == 0:
            break
        hanoi(numOfTray, 'A', 'B', 'C')

참고자료

Related Posts