[Algorithm] 재귀(Recursion)

코딩 테스트를 대비하여 자료구조와 알고리즘에 대해 정리하며 공부 중입니다.
틀린 부분이 있을 수 있다는 점을 감안하고 봐주시기 바라며, 지적은 언제나 환영합니다.

 

🧐 재귀(Recursion)

재귀 함수(Recursive function)는 함수 내에서 자기 자신을 호출하는 함수이다.

함수 내부에서 자기 자신이 호출되면, 자기 자신을 메모리에 복사시켜 놓고 함수를 호출한다.

그리고 반드시 함수가 무한 루프에 빠지지 않기 위해서는 base case를 설정해주어야 한다.

 

* base case : 함수가 더 이상 자기 자신을 호출하지 않도록 설정하는 조건을 의미한다.

 

# 인수 N의 팩토리얼을 구하는 재귀 함수 (python)

def factorial(N):
  if (N == 1):  # base case (탈출 조건)
    return 1
        
  return N * factorial(N -1)  # 자기 자신을 다시 호출한다.(재귀)

 

📎 장점

- for문, while문 등의 반복문과 변수 사용 횟수를 줄여서, 비교적 간결하게 코드를 작성할 수 있다.

 

📎 단점

- 함수가 호출될 때마다 매개변수와 리턴 값, 돌아갈 위치 등이 process stack에 쌓이게 된다.

  -> 공간 복잡도가 증가하고, 스택 오버플로우가 발생할 수도 있다.

- 호출이 끝나고 복귀할 때, Context switching으로 인한 Overhead가 발생할 수 있다.

 

* Context Switching : 멀티 프로세스 환경에서 CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선순위의 프로세스가 실행되어야 할 때 기존의 프로세스의 상태 또는 레지스터 값(Context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값(Context)를 교체하는 작업을 Context Switch(Context Switching)라고 한다.

 

---

🧐 꼬리 재귀(Tail Recursion)

위에서 설명한 재귀 함수의 단점을 보완하기 위해 꼬리 재귀(Tail Recursion)라는 방법이 있다.

꼬리 재귀란,재귀 호출이 끝나면 아무 연산도 하지 않고 오직 결과만을 반환하도록 하는 방법을 말하는데,

결국 재귀 함수가 호출될 때마다 사용한 스택(Stack) 공간을 재사용할 수 있게 되는 것이다.

(반환 값이 더이상 변할 여지가 없다고 컴파일러가 판단을 할 수 있기 때문.)

 

따라서, 꼬리 재귀 방식으로 함수를 구현하게 되면 메모리의 낭비를 막아주어서 스택 오버플로우가 발생할 확률을 낮춰준다.

(다만, 꼬리 재귀는 컴파일러가 지원을 해줘야만 한다.)

# 꼬리 재귀 함수
# return 문에서 (+, -, *, /) 와 같은 부가적인 연산을 하지 않는다.

def factorial_tail(N, value):
  if (N == 1):  # base case (탈출 조건)
    return 1
    
  return factorial_tail(N - 1, value + N)  # 연산을 하지 않고 return

일반 재귀와 다르게 반환하면서 연산하지 않기 때문에 Overhead를 낮출 수 있다.