[자료구조 멘토링] 함수의 재귀 (feat. Python)

1. 함수의 재귀적 호출의 이해

1-1. 재귀란?

재귀는 어떤 함수가 자기 자신을 다시 호출하는 방식을 의미한다.

쉽게 말해서, 어떤 문제를 해결 할 때, 작은 문제로 나누고, 그 작은 문제를 해결하는 방식이 동일하다면 재귀를 사용할 수 있다.

 

1-2. 재귀 함수의 기본 구조

재귀 함수를 작성할 때, 두가지 중요한 요소가 있다.

기본 조건

무한히 자기 자신을 호출하면 안되니깐, 탈출 조건(종료 조건)이 필요하다.

이 조건이 없으면 무한 루프에 빠져서 프로그램이 멈추지 않게 된다.

 

재귀 호출

자기 자신을 호출하는 부분이 필요하다.

이때, 문제의 크기를 점점 줄여서 기본 조건에 도달할 수 있도록 만들어야 한다.

 

1-3. 예제) 펙토리얼 함수

팩토리얼은 자연수 n에 대해서 아래와 같이 정의할 수 있다.

n != n x (n-1)!

 

단, 0! = 1로 정의된다.

 

코드로 작성해보면 아래와 같이 작성할 수 있다.

def factorial(n):
	if n == 0:
    	return 1
	return n *factorial(n-1)
    
print(factorial(5))

실행 흐름을 살펴보면 아래와 같이 나타낼 수 있다.

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1

 

2. 재귀의 활용

재귀는 다양한 문제 해결에 활용될 수 있어. 대표적으로 피보나치 수열을 다룰 수 있다.

2-1. 피보나치 수열

피보나치 수열의 경우 아래와 같이 정의된다.

F(n) = F(n-1) + F(n-2)

단, 기본조건은 아래와 같이 주어진다.

F(0) = 0, F(1) = 1

 

코드로 작성해보면 아래와 같이 작성할 수 있다.

def fibonacci(n):
    if n == 0:  
        return 0
    elif n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(6))  # 8

하지만, 위 방식은 같은 값을 여러번 계산하기 때문에 비효율적이다.

이를 위해서 아래와 같이 메모리제이션(캐싱)을 활용할 수 있다.

memo = {}

def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2) 
    return memo[n]


print(fibonacci_memo(5))

 

3. 주의점

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

• 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있다.

b. 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다. 반복문이 더 유리한 경우도 있다.

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

• 스택 라이브러리 대신 재귀함수를 이용하는 경우가 있다.

 

4. 문제 풀어보기

https://www.acmicpc.net/problemset?sort=ac_desc&algo=62