[이것이 코딩 테스트다 with Python]_17_재귀 함수

220202 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=gFpKGWdEE5g&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=17 

 

 

 

 

 

1. 재귀함수 (Recursive Function)

: 자기 자신을 다시 호출하는 함수

: 재귀 함수를 호출합니다 -> 문자열을 무한히 출력

: 어느정도 출력하다가 초과 메시지가 출력

: 모든 재귀 함수는 반복문을 이용하여 동일한 기능 구현 가능!

: 함수를 연속적으로 호출하면 메모리 내부에 스택 프레임에 쌓임

-> 스택 라이브러리 대신 재귀 함수 이용하기도 함!

 

ex) 재귀함수 -> error 초과!

def recursive_function() :
    print("재귀 함수 호출")
    recursive_function()

recursive_function

 

 

ex) 종료 조건 포함한 재귀 함수

: 재귀 함수의 종료 조건 반드시 명시

: like 스택 처럼

def recursive_function(i) :
    if i == 100 :
        return

    print(i, "번째 재귀 함수에서", i+1, "번째 재귀 함수를 호출합니다")
    recursive_function(i+1)
    print(i, "번째 재귀 함수를 종료합니다")
recursive_function(1)

 

 

 

 

2. 팩토리얼

: n! = 1 x 2 x ... x ( n-1 ) x n

: 0! 과 1! 은 1

# 단순 반복
def factorial_iterative(n) :
    result = 1

    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)

print("단순 반복 : ", factorial_iterative(5))
print("재귀 함수 : ", factorial_recursive(5))

 

 

 

 

 

 

3. 최대 공약수 (유클리드 호제법)

: 두 개의 자연수에 대한 최대 공약수를 구하기

: 재귀 함수로 가능

 

: 유클리드 호제법

- 두 자연수 A, B,에 대하여 ( A > B ) A를 B로 나눈 나머지를 R

- A, B의 최대공약수는 B와 R의 최대공약수와 같다

단계	A	B
1	192	162
2	(B) 162	(나머지) 30
3	30	(나머지) 12
4	12	(나머지) 6
5	6	0

def gcd(a, b) :
    if a % b == 0:
        return b
    else :
        return gcd(b, a%b)
print(gcd(154,22))

# 22