본문 바로가기
Computer science

[알고리즘] 재귀란 무엇일까, 재귀 기초 코드 작성해보기

by Jiyoon-park 2020. 11. 10.

recursion

순환 or 재귀. 자기 자신을 호출하는 것.

  • 무한 루프에 빠지지 않으려면 어떻게 해야하나?

    • base case(적어도 하나의 recursion에 빠지지 않는 경우)가 존재해야 한다.
    • recursive case는 반복하다보면 결국 base case로 수렴해야 한다.
  • 순환함수 == 수학적 귀납법

def f(n):    # 0~n 까지의 합을 구하는 함수
    if n == 0:                # 만약 n == 0 : 합은 0
        return 0
    else:
        return n + f(n-1)    # 만약 n > 0 : 합은 n + (0부터 n-1까지 의 합)
  • factorial
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)
  • x ** n
def f(n):
    if n == 0:
        return 1
    else:
        return x * f(n-1)
  • fibonacci num
def fibo(n):
    if n == 0:
        return 0
    elif n == 1:    # 이거 n <= 1: return n 으로 해도 될 듯
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

  • 최대공약수
# 내 처음 풀이
def gdc(n, m):
    global res
    if n == 0 or m == 0:
        return 1
    else:
        for i in range(min(n, m), 1, -1):
            if n % i == 0 and m % i == 0:
                res *= i
                return gdc(n//i, m//i)
            else:
                continue

res = 1
gdc(54, 63)
print(res)
# better한 풀이
def gdc(n, m):
    if n > m :
        n, m = m, n
    if m % n == 0:
        return n
    else:
        return gdc(n, m%n)

res = gdc(54, 63)
print(res)
# (내 기준)best한 풀이
def gdc(n,m):
    if m == 0:
        return n
    else:
        return gdc(m, n%m)

'Computer science' 카테고리의 다른 글

[HTTP] 인터넷 프로토콜이 뭐야?(IP, TCP, UDP)  (1) 2021.12.24
HTTP란 무엇인가? 알아보자!  (1) 2021.12.24
OS에 대한 기본 개념  (0) 2020.11.21
비전공자 CS 공부 시작  (0) 2020.11.07