1. Recursion - 재귀함수

재귀함수란 자기 자신을 호출하는 함수다.
재귀함수는 반복문(loop)과 스택(stack) 구조가 결합된 함수라고 할 수 있다.

재귀함수를 사용할 때 장점으로는 반복문을 중첩해서 코드를 쓸 때보다 코드가 한층 간결해진다는 점이다.

하지만, 재귀함수는 일반적으로 이해하는데 상대적으로 높은 정신력을 써야 하므로 유지보수가 어려워질 수 있다.
또한, 재호출된 함수가 쌓임으로써(이는 스택 형태로 쌓여있다) 메모리를 더 사용한다고 한다.

재귀함수를 모르는 것보다 이해하고 있으면 당연히 좋다.
재귀함수를 이해하려고 노력하면서 코딩 스킬의 하나로서 익숙해져 있으면 좋을 것이다.

바로 코드를 통해 알아본다.

2. sum(num)

먼저 for문을 활용해 수들을 반복적으로 합해주는 코드를 짜본다.

def sum(num):
    sum = 0
    for i in range(1, num + 1):
        sum = sum + i
    return sum

sum(100)
# 5050
sum(10)
# 55

위와 동일한 결과값을 반환하지만 이번엔 재귀함수를 활용해본다.

def sum_recursion(num):
    if num == 1:
        return 1
    elif num <= 0:
        return None
    
    return oneto100(num-1) + num

3. GCD, LCM - 최대공약수, 최소공배수

다음은 최대공약수와 최소공배수를 다양한 방식으로 구해본다.

1) for loop - for문

# 최대공약수
def gcd(num1, num2):
    for i in range(min(num1, num2), 0, -1):
        if num1%i == 0 and num2%i == 0:
            print(i)
            break
gcd(9, 24)
# 3

# 최소공배수
def lcm(num1, num2):
    for i in range(max(num1, num2), (num1*num2)+1):
        if i%num1 == 0 and i%num2 == 0:
            print(i)
            break
lcm(2, 20)
# 20

2) Euclidean algorithm - 유클리드 호제법

# GCD - 최대 공약수
"""
x%y=r 일때,
x와 y의 최대공약수 == y와 r의 최대공약수

(예시)
x=10, y=12

x % y == r
10%12 == 10
12%10 == 2
10%2 == 0 #나머지 값이 0일때의 y값이 최대공약수
# gcd = 2
"""

def GCD_Euc(num1, num2):
    while num2: #num2==자연수 즉, num1%num2 != 0 
        num1, num2 = num2, num1%num2
    return num1 #마지막 단계에서 num1 자리가 전단계의 num2(gcd)가 되니까

GCD(10, 12)
# 2
GCD(40, 60)
# 20
GCD(7, 19)
# 1 

#LCM - 최소공배수
"""
x * y를 최대공약수로 나눈 몫 == 최소공배수

(예시)
x=10, y=12

gcd(10, 12) == 2
10*12 // 2 == 60 #몫
lcm(10, 12) == 60
"""

def LCM_Euc(num1, num2):
    lcm = (num1*num2) // GCD(num1, num2)
    return lcm   
    
LCM(10, 12)
# 60

1) recursion - 재귀함수

# GCD - 최대공약수
def GCD_recursion(num1, num2):
    
    if num2 == 0:
        return num1
    else:
        return GCD_recursion(num2, num1%num2)
        
GCD_recursion(112, 189)
# 7

4. Factorial

def factorial(n):
    if n > 0:
        return n * factorial(n-1)
    else:
        return 1 #factorial(0) 되는 경우

factorial(10)
# 3628800

5. practice

def countdown(n):
    if n == 0:
      print('Boom!')
    else:
      print(n)
      countdown(n-1)

countdown(3)
#
3
2
1
Boom!

def heart(n):
    if n == 0:
      return None
    else:
      heart(n-1)
      print('💜'*n)

heart(5)
#
💜
💜💜
💜💜💜
💜💜💜💜
💜💜💜💜💜

Created on Nov 25, 2021

• 글 작성