[알고리즘] 재귀 용법(recursive call, 재귀 호출) 알아보기

안녕하세요😎 백엔드 개발자 제임스입니다 :)

오늘은 재귀 용법 또는 재귀 호출에 대해서 포스팅하려고 합니다.

이 재귀 용법은 어떻게 보면 중요한 개념인데요. 앞으로 알고리즘을 학습하다 보면 굉장히 많이 접하기 때문입니다.

이제 자세하게 알아보도록 하겠습니다.

 

---

---

재귀 용법 (recursive call, 재귀 호출)

---

• 재귀는 자기 자신을 참조하는 것
• 함수 안에서 동일한 함수를 호출하는 형태
• '재귀 함수'라고도 함
• 코드의 가독성이 좋음
• 스택 메모리 사용

예시 형태

public int sum(int num) {

	*
	* // 생략
    *
    
	return sum(num-1);
}

위 코드 내용처럼 함수 안에서 자신을 호출하는 방식입니다. 단, 재귀 함수를 사용할 때 호출시마다 입력값(파라미터)은 변합니다. 그리고 위 코드에서는 생략되었지만, 재귀 함수에서 꼭 중요한 것이 있습니다.

위 코드처럼 자신을 계속 호출한다면, 끝없이 무한하게 반복하게 됩니다. 따라서 이를 해결하기 위해 어떠한 조건에서 함수를 종료시켜주어야 합니다.

자세하게 알아보기 위해서 예시를 들어 설명하도록 하겠습니다.

 

01. 재귀 용법을 활용한 예시

1부터 5까지의 합 구하기

이제 코드를 작성해서 1부터 5까지의 합을 구해보도록 하겠습니다.

재귀 용법을 활용하기 전에, 우리가 잘 알고 있는 for문(반복문)으로 구현할 것인데요. 아래 코드를 보도록 하겠습니다.

 

 

---

for 문으로 구현한 코드

int num = 5;
int result = 0;

for( int i = 1; i <= num; i++ ) {

	result += i;
}

System.out.println(result);

for문으로 구현한다면, 위 코드와 같이 구현할 수 있는데요. 이제 이것을 재귀 용법으로 어떻게 만들 수 있을까요?

먼저 메서드를 구현해야 하는데요. 이때 해당 메서드가 재귀 함수가 됩니다.

메서드는 5 + (5-1) + (5-2) + (5-3) + (5-4)와 같은 형태로 진행이 되어야 합니다. 여기서 5는 메서드를 선언할 때 넘긴 인자입니다. 즉, 메서드의 이름을 sum이라고 가정하면 선언 시에 sum(5)를 작성합니다.

---

재귀 함수로 구현한 코드

public int sum(int n) {
	
    // n이 1 이하일 때 재귀함수를 종료(1을 리턴)
    if(n <= 1) {
        return 1;
    }

	// 함수 자신을 반환
    return n + sum(n-1);
}

보다시피 아주 간단해 보이는데요. 이러한 함수가 반복문과 유사한 결과를 나타냅니다.

해당 메서드는 넘겨받은 n을 또 한 번 해당 메서드를 호출하며 값을 더 더하고, 반환합니다.

다시 한번 반복하여 말하자면, 이와 같은 형태가 재귀 함수입니다.

이제 원리를 자세하게 분석하겠습니다.

 

 

---

▶ 해당 메서드를 사용할 때 정수 n을 받습니다. 여기서 예시로 5를 받았다고 가정하겠습니다.

• Sum(5) 
• 먼저 if문에서 n이 1 이하인 조건에 맞지 않기 때문에 내부로 들어가지 않습니다.
• 곧바로 return(반환)을 하게 됩니다.
• return 5 +sum(4)
• 이때 sum(4)의 결과값을 반환받아야 합니다.

▶ 이번엔 인자를 4로 넣어서 다시 메소드의 과정을 진행합니다.

• n 이 1보다 크므로 내부로 들어가지 않습니다.
• 이번엔 return 4 + sum(3) 을 진행합니다.
• 역시 sum(3)의 결과값을 반환받습니다.

▶ 인자를 3으로 넣어서 메서드를 진행합니다.

• 역시나 1보다 큰 n이므로 if문으로 들어가지 않습니다.
• return 3 + sum(2) 을 진행합니다.
• sum(2)의 결과값을 반환받습니다.

▶ 인자를 2로 넣어서 메서드를 진행합니다.

• 이번에도 앞 과정과 동일하게 if문 밖에 있는 return을 진행합니다.
• return 2 + sum(1)
• sum(1)의 결과값을 반환받습니다.

▶ 인자를 1로 넣어서 메서드를 진행합니다.

• 이제는 n이 1 이하이기 때문에 if문 내부로 들어갑니다.
• if문에는 return n이 있습니다.
• 따라서 1을 반환하고, 메서드가 종료됩니다.(이는 재귀 함수가 종료된 것과 동일합니다.)

▶ 복귀

→ 이제 sum(1)이 1을 반환합니다. 재귀 함수는 이렇게 최종에서 값이 반환되면 더 이상 순회를 하지 않고 상위 과정으로 돌아가는데요. 즉, sum(2)가 2 + 1 을 반환하게 됩니다. 이어서 sum(2) 도 반환을 했으므로, sum(3)은 3 + 3 을 반환합니다. 이렇게 가장 처음 함수를 선언했던 sum(5)까지 올라갑니다. 그리고 모두 적용했을 때 5 + 10 이 되면서 sum(5)는 15가 됩니다. 이것은 풀어보면, 5 + 4 + 3 + 2 + 1 과 동일합니다.

재귀 함수의 동작 원리

 

---

 

02. 스택처럼 관리되는 재귀 함수 내부

재귀 함수는 우리가 앞에서 학습했던 스택으로 설명할 수도 있습니다.
<스택(Stack)을 자세하게 보고 싶은 분은 아래 링크를 클릭해주세요.>

https://kang-james.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90Queue%EC%99%80-%EC%8A%A4%ED%83%9DStack-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0

[자료구조] 큐(Queue)와 스택(Stack) 알아보기

 

---

위에서 예시로 보였던 sum(5)를 보도록 하겠습니다.

메소드를 진행할 때 재귀 함수들은 위 그림처럼 메모리에 쌓이게 되는데요. 스택의 정의에 따라 아래서부터 차근차근 쌓이게 됩니다.

우리가 작성한 종료 조건에 도달했을 때가 스택 메모리 가장 위에 존재하는 값이 됩니다. 여기서는 sum(1)이 되는데요. 이제 쌓여있는 데이터를 하나씩 꺼내면서 반환 값을 아래에 있는 함수로 전달합니다. 꺼내는 과정은 아래와 같습니다.

마치 유리병에서 뭔가를 꺼내듯이, 값을 반환하며 함수들을 순차적으로 꺼냅니다. 최종적으로는 마지막 함수가 빠져나갈 때 우리가 원하는 결과값을 얻게 됩니다.

---

03. 재귀 용법(함수) 활용

재귀 용법 및 함수는 많은 곳에서 활용될 수 있는 기법입니다. 피보나치수열, 팩토리얼( ! ) 등 연산할 때 활용되거나 탐색, 정렬, 기타 알고리즘에서 활용됩니다.

그리고 코딩 테스트를 공부하다 보면 하노이 관련된 문제를 접하게 되는데요. 제 기억에는 난이도도 있고, 재밌는 문제였던 것 같습니다.^^

 

 

하노이 문제 재귀 용법 풀이 예시

---

package test.BJ.recursiveFunction;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class HanoiTower_11729 {

    static StringBuilder sb = new StringBuilder();

    static void move(int N, int start, int mid, int end)  {

        if(N==1) {
            sb.append(start + " " + end).append("\n");
            return;
        }

        move(N-1,start,end,mid);
        sb.append(start + " " + end).append("\n");
        move(N-1,mid,start,end);
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 원판의 개수 입력

        sb.append((int) (Math.pow(2,N)-1)).append("\n");

        move(N,1,2,3);

        System.out.println(sb);


    }
}

---

04. 시간(공간) 복잡도

• factorial(n) 은 n-1번의 factorial() 함수를 호출해서 곱셈을 진행
• 일종의 n-1번 반복문을 호출한 것과 동일
• factorial() 함수를 호출할 때마다 지역변수 n 생성

시간 복잡도 / 공간 복잡도는 O(n-1) 이므로 결국 O(n)과 동일

 

 

* 재귀 함수와 반복문(for문)의 차이

그렇다면 재귀 함수와 반복문의 차이는 무엇일까요? 먼저 사용하는 메모리를 알아보도록 하겠습니다.
재귀 함수는 위에서 알아봤듯이 스택 메모리를 사용합니다. 반면 반복문은 메모리 힙을 사용합니다.

메모리 외에는 코드 길이와 변수 사용률이 달라져서 가독성의 차이를 갖습니다.

두 개중 뭐가 좋다고 확실하게 말하기는 어렵습니다. 단, 상황마다 어떻게 사용하느냐에 따라 효율이 달라지는데요. 재귀 함수를 사용했을 때 장점을 말씀드리자면,

1. 변수 사용 감소
    -> 변경 가능한 상태(mutable state)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄임.
2. 로직에는 크게 영향을 가하지 않고, 인자만을 변경하여 결과값을 얻을 수 있음.
3. 복잡한 로직을 자유롭게 구사할 수 있음.