재귀란?

오늘은 재귀에 대해서 정리해보려고 한다.
재귀는 코테에서 가장 많이 나오는 DFS, BFS를 이해하기 위해서 반드시 알아야 하는 내용이기 때문에 정리한 후에도 계속 여러 예제들을 풀어보면서 습득해야될 것 같다.

 

재귀는 쉽게 말해서 자기 자신을 호출하는 함수이다.

예를 들어, 1부터 10까지 더하여 출력하도록 작업한다면 아래와 같이 for문을 이용하여 출력하는게 먼저 떠오를 것이다.

public class Main {
	public static void main(String[] args) {
		System.out.println(loop());
	}

	public static int loop() {
		int n = 0;

		for (int i = 1; i <= 10; i++) {
			n += i;
		}

		return n;
	}
}

 

그리고 이것을 재귀를 이용하여 작업한다면 아래와 같은 코드로 할 수 있다.

public class Main {
	public static void main(String[] args) {
		System.out.println(recursion(10));
	}

	public static int recursion(int n) {
		if (n == 1) return 1;

		return n + recursion(n - 1);
	}
}

이 예제를 보면 recursion 메서드 안에서 n += recursion(n + 1), 즉 자기 자신을 호출하는 것을 알 수 있다.

그리고 자기 자신을 호출한다는 점에서 뭔가 반복적인 동작을 한다는 것을 눈치챌 수 있을 것이다.

알고리즘 문제를 풀다보면 문제에서 뭔가 비슷한 내용이 꼬리에 꼬리를 무는 형태라면 재귀함수를 이용하여 풀 수 있는지 먼저 고려해봐야 한다.

---

그렇다면 재귀함수를 사용하면 어떤 장점이 있고 단점이 있을까??

 

장점

반복문을 사용하지 않기 때문에 코드가 간결해진다.

- 위의 아주 간단한 예제만 봐도 재귀함수를 이용한게 더 간결해보이지 않나 생각이 든다.

 

단점

속도가 느리다.

- 결국 메서드를 계속 호출하는 것이기 때문에 반복하는 만큼 스택에 쌓이게 된다. 메모리를 그만큼 사용하다보니 속도가 저하될 수 밖에 없다. 심지어 무리하게 호출하면 Stack Overflow 오류가 발생할 수 있다.

하지만 이 문제는 꼬리 재귀를 이용하여 최적화가 가능하다.

---

꼬리 재귀

꼬리 재귀는 호출이 끝나면 결과만 바로 반환하도록 하는 방법이다. 더 설명해도 와닿지 않기 때문에 아래 예제를 통해 자세히 설명해보려고 한다.

재귀함수의 대표적인 예제인 팩토리얼로 설명하려고 한다.

 

아래 코드는 일반적인 재귀함수를 이용하여 구현한 것이다.

	public static int factorial(int n) {
		if (n == 1) return 1;

		return n * factorial(n - 1);
	}

해당 코드가 어떻게 내부적으로 동작되는지 보면, factorial(3)을 호출했다고 가정하자.

재귀함수는 3 * factorial(2) / 3 * (2 * factorial(1))  / 3 * (2 * 1 ) / 3 * 2 / 6 이런식으로 호출 당한 함수가 호출한 함수에게 자신의 결과값을 알려주고, 그 값을 전달받은 함수는 자기가 가지고 있던 값과 계산을 해서 다시 다른 함수에게 전달을 한다.

 

이번에는 꼬리 재귀를 이용하여 아래와 같이 구현했다.

	public static int factorialTail(int n, int result) {
		if (n == 1) return result;

		return factorialTail(n - 1, n * result);
	}

딱 봤을 때 보이는 차이점이 있을 것이다. 바로 매개변수에 계산한 결과값을 가지고 있도록 한 것인데, 위에서 설명했듯이 꼬리 재귀는 호출이 끝나면 결과만 바로 반환하도록 하는 방법이다.

꼬리 재귀가 어떻게 내부적으로 동작되는지 보자. 똑같이 factorialTail(3, 1)을 호출했다고 가정하자.

꼬리 재귀는 factorial(3, 1) / factorial(2, 3) / factorial(1, 6) / 6 / 6 / 6 이런식으로 일반재귀와 다르게 어떤 연산을 하지 않고 값을 전달하는 것을 알 수 있다.

 

 

참고

백준 - 재귀 관련 문제 리스트

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

문제 - 1 페이지