재귀함수의 개념과 사용법

1. 재귀란?

 

 

위 사진은 러시아 인형입니다

러시아 인형의 특징은 동일한 형식을 유지한 채, 모양(데이터)가 바뀌는 양상을 띈다는 것입니다.

이는 러시아 인형이 너무 작아서 다른 인형을 담지 못할 때까지 진행됩니다

 

재귀함수도 동일한 방식을 사용합니다.

더 큰 문제를 풀기 위해 문제를 쪼갤 수 없는 단위까지 쪼갠 뒤, 가장 작은 문제를 해결함으로써, 전체 문제를 해결하는 방식이죠

 

*재귀 자체의 의미는 본디의 것으로 돌아온다는 의미를 담고 있습니다

 

---

 

 

재귀 함수는 다음과 같이 구성되어 있습니다

1. Base case(종료 조건) : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우
2. Recursive case(재귀 단계) : 함수가 자기 자신을 호출하여, 문제를 작은 부분으로 나누어 해결하는 단계

아래 절차를 통해 재귀함수를 풀어서 설명하겠습니다

 

1. 문제를 할 수 있는 한 작게 쪼갠다
2. 작은 문제를 푸는 함수를 구상한 뒤, 자신이 만든 함수가 더 작은 문제를 풀 수 있으리라 믿는다
3. 이제 함수가 작은 문제를 풀 수 있다고 가정했기 때문에 더 큰 문제를 어떻게 풀지 고민한다

 

 

 

아직까지도 너무 추상적인 말 뿐이죠?

핵심은, 재귀 호출의 케이스를 단번에 모두 생각해내는 것이 아니라, '아주 작은 문제'와 '그 나머지'로 분류한 뒤 문제를 푸는 것입니다

 

---

아래에서 예재 코드와 함께 재귀 함수를 구상해봅시다
주어진 문자열을 거꾸로 출력하는 함수를 작성해보겠습니다

 

 

 

 

I. 종료조건(Base Case)

문자열이 2보다 작다면, 그냥 문자열을 반환하면 되겠죠?

 

ex. 's' or ''

def reculsive(string) {
   // Base Case
   if (len(string) < 2) return string;
}

 

 

 

 

 

II. 재귀 조건(Recursive Case)

재귀는 계속해서 자기 자신을 호출하는 함수입니다.

따라서, 가장 먼저 호출된 함수가 아닌, 쪼갤 수 없는 단위가 되었을 때, 비로소 출력이 시작되는 것입니다.

 

 

 

그러면, 천천히 생각해봅시다.

재귀적으로 사고할 때, 필요한 것은 가장 작은 단위와 하나의 큰 덩어리로 보는 것입니다

가장 작은 단위는 문자 하나를 의미합니다. 

 

1. 문자열의 첫 번째 문자를 선택합니다.
2. 나머지 문자열(두 번째 문자부터 끝까지)을 재귀적으로 뒤집습니다.
3. 그리고 첫 번째 문자를 뒤에 붙입니다.

이 과정을 반복하면, 결국 문자열이 거꾸로 뒤집혀서 출력됩니다.

 

전체 코드는 다음과 같습니다

def reculsive(string) {
   // Base Case
   if (len(string) < 2) return string;
    
    // Recursive Case
    return reculsive(str[1:len(string)])) + string[0];
}

여기서 의문점이 들 수 있습니다

‘문자열을 거꾸로 출력하는건 간단하게 반복문을 사용하면 되지 않나요? 그러면, 재귀는 어디에 쓰는건가요?’

 

아래의 자바스크립트 코드를 통해서 답을 할 수 있습니다

Recursive Data Structure

const danielKing= {
  name: {
    firstName: 'Daniel',
    lastName: 'King',
  },
  favorites: {
    foods: [
      'pizza',
      'curry'
    ]
  }
}

 

 

위와 같은 구조를 재귀적 데이터 구조라고 칭합니다
동일한 구조의 작은 버전을 내부에 포함하고 있는 데이터 구조이죠

 

 

 

---

 

 

 

2. 재귀 알고리즘 분석 방법

재귀 알고리즘을 분석하는 방법으로는 하향식 분석과 상향식 분석이 존재합니다.

다음 코드를 통해 재귀 알고리즘의 분석 방법을 알아보겠습니다

 

def recur(n:int) -> int:
    if n > 0:
        recur(n-1)
        print(n)
        recur(n-2)
        
x = 4
recur(4)

 

위 재귀 알고리즘을 하향식으로 분석하겠습니다

 

*하향식 분석이란?
호출시점 기준, 탑다운으로 재귀함수를 분석하는 방식

 

 

• recur(4)가 호출되면 recur(3)을 호출합니다.
• recur(3)은 recur(2)를 호출하고, recur(2)는 recur(1)을 호출합니다.
• recur(1)은 종료 조건에 도달하여 1을 출력합니다.
• recur(3)으로 돌아와 recur(2) 호출이 완료된 후 3을 출력하고, 이어서 recur(1)을 호출하여 1을 출력합니다.
• recur(4)로 돌아와 4를 출력한 뒤, 대기 중이던 recur(2)를 호출합니다.
• recur(2)는 recur(1)을 호출하여 1을 출력하고, 이어서 2를 출력합니다.

 

실행 결과는 다음과 같습니다

1
2
3
1
4
1
2

 

 

다음은 상향식 분석 방법입니다.

하향식 분석과는 반대로 아래쪽부터 쌓아 올리며 분석하는 방법을 상향식 분석이라고 칭합니다.

 

 

recur() 함수는 n이 양수일 때만 실행하므로, 먼저 recur(1)과 recur(2)가 어떻게 실행되는지 알아봅시다

 

recur(1)의 실행과정
1. recur(0)을 실행
2. 1을 출력
3. recur(-1)을 실행

recur(2)의 실행과정
1. recur(1)을 실행
2. 2를 출력
3. recur(0)을 실행

 

 

recur(1)을 실행하면 1을 출력하고

recur(2)를 실행하면, 1을 출력한 뒤, 2가 출력됩니다.

이 작업을 recur(4)까지 수행하면 recur(4)를 출력했을 때 결과를 유추할 수 있습니다

 

 

 

 

Reference

https://medium.com/@daniel.oliver.king/getting-started-with-recursion-f89f57c5b60e

Learning to think with recursion, part 1