DFS & BFS 1(재귀함수)

출처 : (이코테 2021 강의 몰아보기) 3. DFS & BFS
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3

재귀함수

자기 자신을 다시 호출하는 함수
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함
종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있음
EX ) 팩토리얼 구현

코드

#팩토리얼
#반복
def factorial_iterative(n):
    result=1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1,n+1):
        result*=i
    return result
#재귀
def factorial_reCursive(n):
    if n<=1:
        return 1
    return n*factorial_reCursive(n-1)

EX ) 유킬리드 호제법
GCD(A,B)
이때 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자.
이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
GCD(192,162)
=> 1단계 : A=192 B=162
=> 2단계 : A=162 B=30
=> 3단계 : A=30 B=12
=> 4단계 : A=12 B=6

코드

#유클리드 호제법
def gcd(a,b):
    if a % b==0:
        return b
    else:
        return gcd(b,a%b)

print(gcd(192,162))