재귀함수(Recursive Function)

재귀함수란 ?

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

def recursive():
    print('재귀함수')
    recursive()
recursive()
# '재귀함수' 가 무한히 출력된다.

파이썬에서는 한계가 있어 어느 순간 에러메세지가 발생하고 종료된다.

재귀 함수를 문제 풀이에서 사용 할 때는 재귀 함수의 종료 조건을 반드시 명시해야한다.

종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출 될 수 있다.

- 팩토리얼 구현 예제

n! = 1 2 3 ''' (n-1) * n

# for문을 이용하여 반복적으로 구현한 방법
def factorial(n):
    result = 1
    for i in range(1,n+1):
        result *= i
    return result

# 재귀적으로 구현한 방법
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

- 최대공약수 계산 예제 (유클리드 호제법)

두 개의 자연수에 대한 최대공약수(GCD)를 구하는 대표적인 알고리즘으로 유클리드 호제법이 있다

• 유클리드 호제법
  • 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R
  • A 와 B의 최대공약수는 B와 R의 최대공약수와 같다

유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성 할 수 있다.

EX)

GCD(192, 162)

단계	A	B
1	192	162
2	162	30
3	30	12
4	12	6

def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
print(gcd(192,162))
# out = 6

- 재귀 함수 사용의 유의 사항

1. 재귀 함수를 잘 활용 하면 복잡한 알고리즘을 간결하게 작성할 수 있지만 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용해야 한다.
2. 모든 재귀 함수는 반목문을 이용하여 동일한 기능을 구현할 수 있다.
3. 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
4. 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임이 쌓이므로 스택을 사용해야 할때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

today review-
요즘 알고리즘 문제를 풀고 코드를 복습해보는 학습과
정보처리기사 필기 공부를 병행하고 있다.
TIL 정리 하는 것도 놓치지 말자.