1장. 재귀 함수 - 1

1. 팩토리얼(자연수 계승)

1.1 구현

아래 factorial 함수의 문제는 무엇일까

def factorial(n):
    return factorial(n-1) * n
    
for i in range(1, 6):
        print(factorial(i))

1.2 에러 : RecursionError

Traceback (most recent call last):
File "main.py", line 6, in <module>
  print(factorial(i))
File "main.py", line 2, in factorial
  return factorial(n-1) * n
File "main.py", line 2, in factorial
  return factorial(n-1) * n
File "main.py", line 2, in factorial
  return factorial(n-1) * n
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

1.3 수정

def factorial(n):
    if n <= 0:
        return 1
    return factorial(n-1) * n
    
for i in range(1, 6):
    print(factorial(i))

1.4 생각해볼거리

기저 조건(base case, 탈출 조건)이 꼭 0이어야 할까?
아래의 코드처럼 0이 아닌 1 이하일 때, return 1을 해도 결과는 똑같이 나온다.

def factorial(n):
    if n <= 1:
        return 1
    return factorial(n-1) * n
    
for i in range(1, 6):
    print(factorial(i))

하지만 기저 조건은 왜 왜 0 이하여야 할까?

팩토리얼 정의 때문이다.

팩토리얼 : 자연수의 계승 또는 팩토리얼(階乘, 문화어: 차례곱, 영어: factorial)은 그 수보다 작거나 같은 모든 양의 정수의 곱이다.
n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 기호는 느낌표(!)를 쓰며 팩토리얼이라고 읽는다.
특히, 0의 계승은 1로 한다.

1.4 정리

재귀 함수를 정의하여 사용할 때
아래 두 가지 사항을 반드시 고려해야 한다.

1. 어떤 매개변수로 재귀 함수를 호출할 것인가
2. 기저 조건은 무엇인가

---

2. 스택 프레임으로 재귀 함수 이해하기

2.1 원리

재귀 함수는 자기 자신을 호출하면서 어떻게 현재의 매개변수 값 및 그 이전 값들까지 기억하며 작동하는 것일까?

메모리 내 스택 프레임이란 공간을 사용하기 때문이다.
스택 프레임에 함수 실행에 필요한 지역 변수들이 저장된다.

2.2 예시

def add_two(a, b):
	# 지역 변수
	c = a + b
    return c
    
# 전역 변수
a = 10
b = 20

result = add_two(a, b) # 지역 변수
print(result)

• 전역 변수는 프로그램의 라이프 사이클 동안 메모리에 유지되는 정보다.
• 지역 변수는 스택 프레임 공간에 저장된다.

2.3 RecursionError 발생 이유

기저 조건이 없다면 메모리 내 스택 프레임은 계속 증가한다.
하지만 스택 프레임의 크기에는 한계가 있다.

메모리 내 스택 프레임 공간을 생각해본다면, 재귀 함수가 호출하는 지역 변수 역시 스택 프레임 공간 안에 저장된다.

따라서, 기저 조건을 향해가는 (스택 프레임 공간의) 지역 변수를 통해
RecursionError를 방지할 수 있다.

참고로, 함수의 끊임없는 호출로 인해 메모리 내 스택 프레임으로 쓰일 메모리 공간이 모자라게 되는 에러를 stack overflow라고 한다.