재귀

1. 재귀 함수란 자기 자신을 다시 호출하는 함수

2. 단순한 형태의 재귀 함수 예제

   - '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다.

   - 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.

def recursive_function() :
	print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function()

3. 재귀 함수의 종료 조건

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

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

   (3) 종료 조건을 포함한 재귀 함수 예제

def recursive_function(i) :
	# 100번 째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100 :
    	return
    print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)

4. 팩토리얼 구현 예제

   1) n! = 1 x 2 x 3 x ··· x (n-1) x n

   2) 수학적으로 0!과 1!의 값은 1이다.

# 반복적으로 구현한 n!
def factorial_iterative(n) :
	result = 1
    for i in range(1, n+1) :
    	retult *= i
    return result
    
# 재귀적으로 구현한 n!
def factorial_recursive(n) :
	if n <= 1 :     # n이 1 이하인 경우 1을 반환
    	return 1
    # n! = n * (n-1)!를 그대로 코드로 작성하기
    return n*factorial_recursive(n-1)

5. 재귀 함수 사용 시 유의사항

   (1) 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.

      - 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용해야 한다.   

   (2) 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.

   (3) 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.

   (4) 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

      -> 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.