재귀함수(Recursive Function)

재귀 함수(Recursive Function)란?

자기 자신을 직접적이든 간접적으로 다시 호출하는 함수를 재귀 함수라고 한다.

---

🤔 일반함수와 어떻게  다른가?

 

일반적으로 함수는 자신만의 scope(범위)를 가진다.

즉,  함수 안에서 만든 변수나 코드들은 그 함수 안에서만 사용되는 작은 공간을 가진다는 뜻이다.

그리고 함수가 호출되면, 컴퓨터는 그 함수가 실행되기 위한 정보들을 스택(Stack)에 저장해둔다.

 

 

일반 함수는 보통 한 번 호출되고 실행이 끝나면 종료된다.

 

예를 들어,

def hello():
  print('안녕!')

hello()

이 경우 hello()함수는 한 번 실행되고 끝난다.

 

즉, Stack에 함수 실행 정보가 한 번만 쌓였다가 사라지는 것이다.

 

 

반면, 재귀 함수는 함수 안에서 자기 자신을 다시 호출하기 때문에, 함수 실행 정보가 여러 개 쌓이게 된다.

 

대표적인 재귀함수인 팩토리얼 계산 함수를 한 번 보자 

def fact(n):
  if n==0: return 1
  else:
    return n * fact(n-1)

 

실행 결과

24

 

 

 

이런 식으로 함수가 자기 자신을 계속 호출하게 된다. 

 

그래서 일반 함수와 다르게 같은 함수 실행 정보가 스택(Stack)에 여러 번 쌓이게 된다.
하지만 재귀 함수도 언젠가는 멈추는 조건이 꼭 필요하다.

 

위 코드에서는

if n==1:
    print(f'hello1')
    return

 

이 부분이 Base Case(종료 조건) 역할을 한다.

만약 이런 종료 조건이 없다면, 함수가 계속 자기 자신을 호출하게 되고, 결국 오류가 발생할 수 있다.

---

재귀 함수의 장점과 단점

장점

1️⃣  특정 상황에서는 시간 복잡도를 개선할 수 있다.

한가지 주의해야 할 것은 재귀 함수 자체가 무조건 빠른 것은 아니다. 오히려 같은 계산을 여러 번 반복하면, 반복문보다 더 느려질 수도 있다.

하지만 memoization(이미 계산한 값을 저장해 재사용하는 방식) 과 함께 재귀함수를  사용하면, 중복 계산을 줄여 시간 복잡도를 개선할 수 있다.

 

예를 들어 피보나치 수열을 일반 재귀 함수로 구현하면 같은 값을 여러 번 계산하게 되지만, memoization을 사용하면 이미 계산한 값을 저장해서 재사용할 수 있다.

2️⃣  코드가 더 간결하고 구조를 이해하기 쉬울 수 있다.

재귀 함수는 문제를 작은 문제로 나누는 구조를 표현할 때 코드가 훨씬 간단해질 수 있다.

---

단점

1. 재귀 함수는 메모리를 더 사용할 수 있다.

재귀 함수는 함수가 자기 자신을 계속 호출하는 구조이기 때문에, 함수가 호출될 때마다 실행 정보를 스택(Stack) 에 저장하게 된다. 그리고 이 정보들은 함수 실행이 모두 끝날 때까지 메모리에 남아 있게 된다.

그래서 반복문(iteration)처럼 한 공간을 계속 사용하는 방식보다 메모리를 더 많이 사용할 수 있다.

 

특히, 재귀 호출이 너무 깊어지면 Stack Overflow(스택 오버플로우) 와 같은 오류가 발생할 수도 있다.

2. 재귀 함수는 더 느려질 수도 있다.

재귀 함수는 함수가 호출될 때마다 새로운 함수 실행 과정이 추가된다.
이 때, 함수 호출이 여러 번 발생하면서 그만큼 오버헤드(추가 비용) 가 발생할 수 있다.
특히 같은 계산을 여러 번 반복하는 재귀 함수는 반복문보다 오히려 더 느려질 수도 있다.

간단한 재귀 예제

1부터 n까지의 정수를 더하는 것을 재귀함수로 표현해보면 아래와 같이 구현해볼 수 있다.

def sum(n): 
  if n==1 :
    return 1
  else: return (n+ sum(n-1))

print(f'sum(10)={sum(10)}')

실행 결과

 

sum(10)=55