재귀 알고리즘(파이썬)

 

 

 

재귀 알고리즘

---

 

 

 

 

재귀 함수

호출한 함수 안에서 그 함수를 다시 호출(recursive call)함으로 반복하는 것을 의미한다. 쉽게 말하면 def를 통해 함수를 만든다. 그리고 만든 함수 안에서 다시 그 함수를 호출하는 것을 의미한다.

 

 

 

반복문 대신 재귀 함수를 이용한 예

def recusion(num):

    if num > 0:
        print('*' * num)
        return recusion(num - 1)
    else:
        return 1

recusion(10)

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

 

 

 

 

재귀 함수를 이용한 팩토리얼 구하기

def factorial(num):

    if num > 0:
        return num * factorial(num - 1)
    else:
        return 1

print(f'factorial(10): {factorial(10)}')

factorial(10): 3628800

 

 

 

 

 

재귀 알고리즘을 이용한 최대 공약수 계산

 

유클리드 호제법

• 두 자연수 n1, n2에 대하여 (n1 > n2) n1를 n2로 나눈 나머지를 r이라고 할 때,
•  n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다

def gcd(n1, n2):

    if n1 % n2 == 0:
        return n2
    else:
        return gcd(n2, n1 % n2)

print(f'gcd(82, 32): {gcd(82, 32)}')
print(f'gcd(96, 40): {gcd(96, 40)}')

gcd(82, 32): 2
gcd(96, 40): 8