Java - Recursive Funtion

Recursive Funtion

 

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

 

재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결

 

반복문과 마찬가지로 재귀함수도 종료지점을 제대로 생각하지 않고 구현 하면 스택오버플로우 발생 (주의 해서 구현)

 

package recursion;

public class Hello {

	public static void main(String[] args) {
		HelloJava(5);

	}
	
	public static void HelloJava(int n) {
		if(n == 0)
			return; //n이 0인 경우 return
		System.out.println("Hello Java");
		HelloJava(n - 1); //재귀함수 시작
	}
}

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

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

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

package recursion;

public class Sum {

	public static void main(String[] args) {
		int N = 5;
		System.out.println("1부터" + N + "까지의 합계 : " + plus(10));
	}
	
	public static int plus(int n) {
		if(n == 0)
			return 0; // n이 0인 경우 return
		return n += plus(n-1); //재귀함수 시작
	}
}

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

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

package recursion;

public class Fibonacci {

	public static void main(String[] args) {
		int n = 10;

		for (int i = 0; i < n; i++) {
			System.out.println(Fibonacci(i) + "");
		}

	}

	private 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 21 34 55...

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

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

package recursion;

public class Array {

	public static void main(String[] args) {
		int arr[] = { 0, 80, 60, 40, 20, 100 };
		System.out.println(ArraySort(arr, 6));
	}

	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];
	}
}

메인 함수(main)에서는 int형 배열 arr을 생성하고, 이 배열의 값을 초기화한 후, ArraySort 함수에 이 배열과 배열의 크기를 매개변수로 전달합니다.

ArraySort 함수는 다음과 같이 구현됩니다.

1. 만약 배열의 크기(n)가 1이면, 배열의 첫 번째 요소를 반환합니다.
2. 그렇지 않으면, 배열의 첫 번째 요소부터 n-1번째 요소까지 재귀적으로 비교합니다.
3. 비교 과정에서는, n-1번째 요소와 이전 요소들 중 최댓값(x)을 찾습니다.
4. 최댓값(x)이 n-1번째 요소보다 크다면, x를 반환하고 그렇지 않으면 n-1번째 요소를 반환합니다.

즉, 이 코드는 배열에서 최댓값을 찾는 재귀적인 함수를 구현한 것입니다. 이 함수는 배열의 크기가 1이 될 때까지 배열의 요소를 계속 비교하면서, 최댓값을 찾습니다. 최종적으로 반환되는 값은 배열의 최댓값입니다.

메인 함수에서는 이 함수를 호출하고, 반환된 최댓값을 출력하게 됩니다. 따라서, 이 코드를 실행하면 배열 {0, 80, 60, 40, 20, 100}의 최댓값인 100이 출력됩니다.