[JAVA] 재귀함수(Recursion Function) 개념 및 예제

안녕하세요

최근에 알고리즘 공부를 하면서 재귀함수를 응용해서 풀은 문제가 있습니다

실제 회사에서 개발을 하면서 거의 써본적이 없는데 알고리즘을 풀다보면 종종 쓰일 것 같습니다

이번 기회에 재귀함수에 대해서 개념 및 예제를 정리해보겠습니다

 

목차

재귀함수란?
HelloWorld 반복출력
1 + N까지의 합계출력
파보나치 수열구하기
배열에서 최대값 찾기

 

---

재귀함수란?

함수가 직접 또는 간접적으로 자신을 호출하는 프로세스를 재귀함수라고 합니다

재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결할 수 있습니다

반복문도 마찬가지지만 재귀함수도 종료지점을 제대로 생각하지 않고 구현을 하면 스택오버플로우가 발생할 수 있으니 항시 주의해서 구현을 해줘야합니다

 

---

HelloWorld 반복출력

public class PlusFunction {
	public static void main(String[] args)  {
		HelloWorld(5); // HelloWorld 출력 메서드 호출
	}
	
	// HelloWorld 출력 메서드 선언
	public static void HelloWorld(int n)
	{
		// n이 0인 경우 return
		if(n == 0)
			return;
		
		System.out.println("HelloWorld"); // HelloWorld 출력
		HelloWorld(n-1); // 재귀함수 시작
	}
}

"Hello World"를 반복출력하는 재귀함수입니다

n이 0이 될 때 메서드를 끝을 냅니다

함수를 호출 할 때마다 n을 1씩 빼줘서 재귀함수를 종료하게 만들어줍니다

 

---

1 + N까지의 합계출력

public class PlusFunction2 {
	public static void main(String[] args)  {
		int N = 5;
		System.out.print("1부터 " + N + "까지의 합계 : " + PlusPlus(5)); // PlusPlus 출력 메서드 호출
	}
	
	// PlusPlus 출력 메서드 선언
	public static int PlusPlus(int n)
	{
		// n이 0인 경우 return
		if(n == 0)
			return 0;
				
		return n += PlusPlus(n-1); // 재귀함수 시작
	}
}

1부터 N까지의 합계를 출력하는 재귀함수입니다

Return에서 N += 재귀함수를 호출하여 1부터 N까지의 합계를 구해줍니다

 

---

파보나치 수열구하기

public class FibonacciFunction {
	public static void main(String[] args)  {
		int n = 10;
		
		for(int i = 0; i < n; i++) // 피보나치 수열 출력
			System.out.print(Fibonacci(i) + " ");
	}
	
	// 피보나치 수열의 결과를 구하는 메서드 선언
	public static int Fibonacci(int n)
	{
		if(n == 0)
			return 0;
		
		if(n == 1 || n == 2)
			return 1;
		
		else 
			return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

피보나치 수열은 1 1 2 3 5 8 13...

이런식으로 N = (N - 1) + (N - 2) 이 계속해서 나오도록 하는 수열입니다

위처럼 재귀함수를 사용 피보나치 수열을 구할 수 있습니다

 

---

배열에서 최대값 찾기

public class ArrayFunction {
	public static void main(String[] args)  {
		// 배열의 최대값을 가져온다
		int arr[] = {0, 80, 60, 40, 20, 100};
		System.out.println(ArraySort(arr, 4));
	}
	
	// 크기가 N인 경우 최대값을 가져오는 메서드 선언
	public static int ArraySort(int[] a, int n)
	{
		int x;
		if(n == 1)
			return a[0];
		else
			x = ArraySort(a, n - 1);
		
		if(x > a[n - 1])
			return x;
		else
			return a[n - 1];
	}
}

재귀함수를 응용 배열에서 최대값을 찾는 메서드입니다

 

재귀함수를 응용하여 다양한 문제를 해결할 수 있습니다

이상 재귀함수에 대해서 알아봤습니다!

이 포스팅이 자바를 공부하는 분들께 도움이 되었으면 좋겠습니다