재귀(Recursion)와 스택(stack)영역

다른 알고리즘과는 다르게 제목에 재귀와 함께 스택 영역을 적어놓은 이유가 있다.
재귀 함수를 호출하는 것과 메모리 스택 영역의 연관성은 마지막 부분에 정리하겠다.

1.1 재귀(Recursion)

* 위키피디아 정의
컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 프로그래밍에서는 함수가 자기 자신의 함수를 호출하도록 구현한다. 보통 알고리즘을 구현할 때, 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 더 직관적이고 이해하기 쉬운 경우가 많다.

재귀는 마치.. 무의식 속의 무의식으로 들어갔다가 결국 현실로 되돌아오는 인셉션과 비슷하다.

위키피디아

용어만으로는 헷갈리니 파이썬 코드로 알아보자.

def recursion():
	print("난 재귀 함수야")
    recursion()

recursion() 		# 함수 호출

recursion 함수 안에서 자기 자신인 recursion 함수를 호출하고 있는데, 이것이 재귀 함수이다. recursion 함수가 자기 자신을 계속 호출하다가 파이썬이 정한 최대 재귀 깊이를 초과하여 RecursionError가 발생했다.
즉, 재귀 함수는 종료 조건을 설정하지 않으면 무한하게 자기 자신을 호출하게 된다.

출처: 파이썬 코딩 도장

그래서 재귀 함수를 사용하려면 반드시 종료 조건을 생성해주어야 무한 반복에 빠지지 않는다.

1.2 재귀 호출로 팩토리얼 구하기

팩토리얼(factorial): 1부터 n까지의 모든 자연수의 곱이다.

파이썬으로 팩토리얼 재귀 함수를 만들어서 팩토리얼을 구해보자.

def factorial(n):
    if n == 1:     		   # n이 1일 때
        return 1   		   # 1을 반환하고 재귀호출을 끝냄
    
    else:
    	return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
 
print(factorial(5))

------------------------------------------------------------------------------------------
# 아래는 for 반복문으로 구현한 팩토리얼

def factorial(n): 
    result = 1
    
    for i in range(1, n+1):
        result *= i
    return result
    
    
print(factorial(5))

출처: 파이썬 코딩 도장

factorial 함수의 핵심은 반환값이다.
계산 결과가 즉시 구해지는 것이 아니라 재귀호출로 (n - 1)을 계속 전달하다가 종료 조건인 n이 1일 때의 값 1을 반환하면서 n과 곱하고 다시 결괏값을 반환하는 과정을 반복한다.

출처: 파이썬 코딩 도장

재귀 함수의 마지막 호출은 if n == 1: 을 종료 조건을 만나서 1을 반환한다. 그 뒤 1과 2를 곱해서 2를 반환하고, 3과 2를 곱해서 6을 반환하고, 4와 6을 곱해서 24를 반환하고, 5와 24를 곱해서 120을 반환하게 된다.

출처: 파이썬 코딩 도장

---

💻 재귀 함수와 스택 메모리

재귀 함수에서는 동일한 함수를 계속해서 호출될 때마다 함수를 위한 메모리가 계속해서 할당된다. 함수가 호출될 때마다 사용되는 임시 저장 메모리를 스택이라고 부른다.
스택은 LIFO(후입선출) 구조이기 때문에 가장 마지막에 호출된 함수 factorial(1)를 먼저 완료하고, 값을 아래로 전달하여 최초로 호출된 함수 factorial(3)가 최종 값을 계산한다.
재귀 함수를 이용하다보면 함수가 종료되지 않고, 함수가 계속해서 호출이 되는데 이 경우 스택 공간이 초과되는 스택 오버플로(stack overfolw)가 발생하여 오류가 생긴다. 그렇기 때문에 재귀를 사용할 떄는 과도하게 스택 메모리가 사용되지 않도록 주의해야 한다.

출처: NAVER Connect 모두를 위한 컴퓨터 과학 자료

💻 프로세스 메모리 구조

프로그램이 실행되기 위해서는 먼저 프로그램이 운영체제로부터 메모리 공간을 할당받아야 한다. 따라서 컴퓨터의 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공하는데, 프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간에는 4가지 영역이 존재한다.

코드 영역과 데이터 영역은 프로세스가 실행되기 직전에 위치와 크기가 결정되고 실행되는 동안 변하지 않으므로 정적 할당 영역이라고 부른다.
1. 코드(code) 영역: 실행할 프로그램의 코드가 저장되는 영역
2. 데이터(data) 영역: 프로그램이 사용하려고 미리 정의한 변수와 데이터가 저장되는 영역

스택 영역과 힙 영역은 스레드가 작업하면서 값이 바뀌거나 새로 만들 만들어지거나 사라지는 동적 할당 영역이다.
3. 스택(stack) 영역: 프로세스 실행을 위한 함수의 호출과 관계되는 지역 변수 및 매개변수가 저장되는 영역
4. 힙(heap) 영역: 프로그램이 실행되는 동안 사용자가 직접 메모리를 관리할 수 있는 메모리 영역

이 중에서 스택 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 임시 메모리 영역이다. 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.