재귀 함수란재귀 함수란 함수 내에서 자기 자신을 부르는 함수이다. 개념은 간단한데, 실제로 재귀 함수로 작성된 코드를 보거나 재귀 함수를 이용해 코드를 짜려 하면 막막할 때가 많다. 이 포스트에서는 재귀 함수가 어떻게 동작하는지에 대해 알아보고 아주 간단한 재귀 함수를 구현 해 본다. [예제 1] package com.demo;
public class Application {
public static void main(String[] args) {
Application application = new Application();
application.recursiveFunction();
}
void recursiveFunction() {
System.out.println("Recursive Function.");
recursiveFunction();
}
}
[예제 1]을 실행하면 어떻게 될까? ... Recursive Function. Recursive Function. Recursive Function. Recursive Function. Exception in thread "main" java.lang.StackOverflowError System.out.println을 엄청 많이 실행 한 후, StackOverflowError와 함께 어플리케이션이 종료된다. 무슨 일이 일어난걸까? 재귀 함수가 동작하는 방식[그림 1]  자기 자신을 부른다는 것을 다르게 생각 해 보면 자기 자신의 복사본을 실행하는 것으로 생각 해 볼 수 있다. 재귀 함수의 경우 자기 자신의 복사본을 계속해서 실행하기 때문에, [예제 1]의 경우 스택오버플로우 에러가 아니라면 이 프로그램은 영원히 돌아가는, 무한 루프같은 어플리케이션이 된다. 베이스 케이스이런 사태를 막기 위해 또는 알고리즘의 로직 상 베이스 케이스(Base case)라는 것이 존재한다. 베이스 케이스란 함수가 더 이상 자기 자신을 부르지 않도록 하는 조건문을 의미한다. [예제 2] package com.demo;
public class Application {
public static void main(String[] args) {
Application application = new Application();
application.recursiveFunctionWithBaseCase(3);
}
void recursiveFunctionWithBaseCase(int num) {
if(num == 0) {
System.out.println("베이스 케이스 : " + num);
return;
}
System.out.println("Recursive Function. " + num);
recursiveFunctionWithBaseCase(num - 1);
}
}
[예제 2]를 실행하면 다음과 같은 결과를 확인 할 수 있다. num이 계속해서 재귀함수로 넘어간다. 이 때, 현재 함수는 다음 함수에게 num을 그대로가 아닌 1을 뺀 값을 전달한다. 자기 자신을 계속 부르는 함수는 num에서 계속 1을 빼므로 어느 순간 0이 되고, 베이스케이스의 조건문 if(num == 0)에 걸려 더 이상 자기 자신을 부르지 않고 리턴을 시작한다. Recursive Function. 3 Recursive Function. 2 Recursive Function. 1 베이스 케이스 : 0 [그림 2] [그림 2]을 보자. 메인 메서드에서 recursiveFunctionWithBaseCase(3)을 부른다. num이 3이 아니므로 Recursive Function. 3 을 실행하고, recursiveFunctionWithBaseCase(2)를 부른다. 이 때. 첫 번째로 주의해야 할 점은 num – 1을 한다고 현재의 num의 값이 2로 바뀌는 게 아니라는 점이다. 우리는 그냥 num – 1 값을 매개변수로 전해 줄 뿐이다. 따라서 다음 콜에서는 num이 2이다. 이 num은 이전의 num과는 다른 num이라는 사실에 주목하자. 각 메서드는 원래 메서드의 복사본을 실행한다고 생각 할 수 있다고 했다. 따라서 매개변수 코드도, 메서드의 지역 변수 코드도 모두 복사본인 것이다. 이 복사본 코드는 이전에 실행한 코드랑 전혀 상관 없는 독립된 코드라는 것에 유의하자. 변수의 이름이 같다고 같은 변수가 아니라는 뜻이다. 두 번째로 주의해야 할 점은, 메서드를 실행 한 후 리턴 한다는 것이다. 이 부분은 다른 예제를 통해 보도록 하자. [예제 3] package com.demo;
public class Application {
public static void main(String[] args) {
Application application = new Application();
application.recursiveFunctionWithBaseCase(3);
}
void recursiveFunctionWithBaseCase(int num) {
if(num == 0) {
System.out.println("베이스 케이스 : " + num);
return;
}
System.out.println("Recursive Function. " + num);
recursiveFunctionWithBaseCase(num - 1);
System.out.println("Recursive Function End of Method. " + num);
}
}
[예제 3]과 [예제 2]의 차이는 무엇인가? [예제 3]은 재귀 함수를 부른 수 또 다른 코드를 실행 한다는 것이다. [예제 3]을 실행하면 다음과 같은 결과를 확인 할 수 있다. Recursive Function. 3 Recursive Function. 2 Recursive Function. 1 베이스 케이스 : 0 Recursive Function End of Method. 1 Recursive Function End of Method. 2 Recursive Function End of Method. 3 [그림 3] [그림 3]에서 함수의 각 라인이 실행되는 순서는 번호를 통해 표현했다. 다시 말해 함수가 리턴하고 나면 자기 자신을 부른 함수(Caller)에게 돌아간다. 따라서 키워드 ‘return’인 것이다. void 함수의 경우 return을 명시하지 않아도 함수의 마지막에서 리턴한다. 그 후 Caller 함수는 나머지 부분을 실행한다는 것이다. 재귀 함수가 전부 실행되기 전 까지 Caller함수는 리턴하지 않은, 아직도 실행 중인 상태라는 사실에 유의하자. 함수의 작동 방식에 대한 개념이 명확히 잡히지 않은 경우 이 부분에서 헷갈릴 수 있다. 이것으로 재귀 함수의 기본적 개념에 대해 알아보았다. 재귀 함수는 언제 사용하는가?솔직한 말로 잘 사용하지 않는다. 코딩 인터뷰를 제외하면 프로덕션에 들어가는 코드 중 재귀 함수를 써 본 것은 한 번 정도 였던 것 같다. 그럼에도 불구하고 재귀 함수를 공부하는 이유 또는 재귀 함수의 장점은 다음과 같다.
재귀 함수의 단점은
더 알아보기재귀 함수의 개념에 대해 공부 했으니 실습을 해 보자. 1 + 2 + … + 10 을 모두 더하는 함수를 재귀 함수로 어떻게 작성 할까? [코드 4] package com.demo;
public class Application {
public static void main(String[] args) {
Application application = new Application();
int result = application.sum(10);
System.out.println("1 + 2 + ... + 10 = " + result);
}
int sum(int n) {
if( n == 0 ) {
return 0;
}
return n + sum(n - 1);
}
}
이 코드를 실행하면 다음과 같은 결과가 나온다. 스스로 이 코드가 어떻게 동작하는 지 생각 해 보고 그 과정을 그려보도록 하자. 그 과정은 [그림 4]와 비슷 할 것이다. [그림 4] 맺으며혹시 재귀 함수와 비슷한 것을 수학책에서 본 기억이 나지 않는가? 바로 점화식이다. 재밌게도 위키피디아를 보면 점화식은 ‘재귀식’이라고 불리기도 한다. 또 많은 점화식 문제를 재귀함수로 풀 수 있다는 사실도 알 수 있다. 예를 들어 1에서 10까지 더하는 재귀 함수에서 1에서 n까지 더하는 것으로 하면 그 점화 식은 다음과 같다. a_{n}=a_{n-1} + n \ ,\ a_{0} = 0이는 우리가 짠 재귀함수 sum(10) = sum(10 – 1) + 10과 일치하는 식이다. 재귀 함수에도 베이스 케이스가 있다, 바로 a0 = 0이 베이스 케이스이다. 이렇게 보면 재귀함수는 점화식을 계산하기 위한 함수인 것 같기도 하다. 재귀 함수의 예제로 자주 나오는 피보나치 수열도, 점화식의 대표적인 예이다. 또 재귀 함수를 공부하면 나오는 대표적인 문제, 하노이의 탑도 점화식으로 표현 할 수 있다. 그럼 우리가 점화식을 푸는 것과 재귀 함수와는 무슨 차이가 있을까? 재귀 함수는 그다지 효율적이지 않다. 그래서 10번째 항을 구하고 싶으면 자기 자신을 계속 부르면서 계산을 한다. 우리는 주입식 교육 덕에 점화식을 일반 수열식으로 푸는 방법을 배웠다. 일반 수열 식으로 변형하면 계산은 한번만 하면 된다. 예를 들어 1 + 2 + … + n의 경우 재귀 함수는 함수를 10번 부르지만, 우리는 n(n+1)/2가 식이라는 것을 알고 있다.. [1 + 2 + … + n의 식] \sum_{k=1}^{n} k = \frac{n(n+1)}{2} 이렇게 프로그래밍 언어와 수학 사이의 관계를 알아보는 것도 프로그래밍을 공부에 있어 흥미로운 점인 것 같다. 이런 점을 고려해 다음 포스트에서는 하노이의 탑을 알아보도록 한다. |
재귀함수 짜는 법 - jaegwihamsu jjaneun beob
관련 게시물
저작권 © 2024 ko.apacode Inc.
