[알고리즘] 자바에서의 재귀 호출(Recursive Call) # 1

재귀 용법(Recursive Call, 재귀 호출)

- 고급 정렬 알고리즘에서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 학습하는 것이 좋다.

- 함수 안에서 동일한 함수를 다시 호출하는 형태이다.

- 재귀 용법은 다른 알고리즘과는 달리 코드를 작성하느 일정한 패턴이 있다.

- 재귀 함수는 내부적으로 스택처럼 관리된다.

 

 

재귀 호출을 이용해 팩토리얼을 구하는 알고리즘을 작성해보자.

- 팩토리얼의 경우 결과값을 구하기 위한 일정한 규칙이 있다.

- n! = n * (n - 1)!

- 메소드로 만들 경우 메소드(n) 은 n > 1 이면 return n * 메소드(n - 1), n = 1 이면 return n

 

* 코드로 작성해보자.

- Factorial.java

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

public class Factorial {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		bw.write("데이터를 입력하세요 : ");
		bw.flush();
		int data = Integer.parseInt(br.readLine());
		
		bw.write("팩토리얼 계산 결과 : " + fac(data) + "\n");
		bw.flush();
		bw.close();	
	}
	
	private static int fac(int data) {
		if(data <= 1)
			return data;
		else {
			return data * fac(data-1);
		}
	}
}

 

재귀 호출의 시간 복잡도와 공간 복잡도

- fac(n) 은 n - 1 번의 fac() 함수를 호출해서 곱셈을 한다.

    - 일종의 n - 1 번의 반복문을 호출한 것과 동일하다.

    - fac() 함수를 호출할 때마다 지역변수 n 이 생성된다.

- 시간 복잡도/공간 복잡도는 O(n-1) 이므로, 결국 둘 다 O(n) 이다.

 

* 재귀 호출은 다음과 같은 두 가지 형태로 활용할 수 있다.

- case 1

private static int function(int data){
	if (data > 1) // 입력이 일정값 이상이면
		return data + function(data-1); // 입력 보다 작은값을 파라미터로 함수 재귀 호출
	else
		return 1; // 재귀호출 종료

- case 2

private static int function(int data){
	if(data <= 1)
		return 1;
	else
		return data + function(data-1);
}

 

 

몇 가지 예제를 더 풀어보자.

- 회문(Palindrome) 은 순서를 거꾸로 읽어도 제대로 읽은것과 같은 단어와 문장을 의미한다.

- 회문을 판병할 수 있는 함수를 문자열 슬라이싱을 활용해서 만들어보자.

- 문자열을 입력받고 회문이면 true, 아니면 false 를 리턴하는 코드를 작성해보자.

 

- PalindromeCase1.java

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

public class PalindromeCase1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		bw.write("문자열을 입력하세요 : ");
		bw.flush();
		String str = br.readLine();
		if(palindrome(str, reverse(str)))
			bw.write("입력하신 문자열은 회문(palindrome) 입니다.\n");
		else
			bw.write("입력하신 문자열은 회문(palindrome) 이 아닙니다.\n");
		
		bw.flush();
		bw.close();
	}
	
	private static String reverse(String str) {
		if(str.length() == 1)
			return String.valueOf(str.charAt(0));
		else
			return String.valueOf(str.charAt(str.length()-1)) +
					reverse(str.substring(0, str.length()-1));
	}
	
	private static boolean palindrome(String str1, String str2) {
		if(str1.equals(str2))
			return true;
		else
			return false;
	}
}

- 입력 받은 문자열을 reverse() 메소드를 통해 거꾸로 돌려버린다.

- reverse() 메소드 내부에서 재귀 호출을 할 때 파라미터 값으로 문자열의 가장 뒤에 있는 요소를 잘라낸 결과값을 준다.

- 계속 문자열의 뒤를 잘라낸 결과 문자열의 길이가 1이 될 경우 해당 문자열을 반환해주면서 재귀 호출을 종료시킨다.

- reverse() 메소드를 통해 거꾸로 뒤집어진 문자열과 원래 문자열을 비교하여 회문인지 아닌지 판별한다.

 

- PalindromeCase2.java

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

public class PalindromeCase2 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		bw.write("문자열을 입력하세요 : ");
		bw.flush();
		String str = br.readLine();
		if(palindrome(str))
			bw.write("입력하신 문자열은 회문(palindrome) 입니다.\n");
		else
			bw.write("입력하신 문자열은 회문(palindrome) 이 아닙니다.\n");
		
		bw.flush();
		bw.close();
	}
	
	private static boolean palindrome(String str) {
		if(str.length() <= 1)
			return true;
		else if(str.charAt(0) == str.charAt(str.length()-1))
			return palindrome(str.substring(1, str.length()-1));
		else
			return false;
	}
}

- palindrome() 메소드에서 입력받은 문자열의 첫번째 인덱스와 마지막 인덱스를 비교한다.

- 비교 결과 true 일 경우 문자열의 첫번째 인덱스와 마지막 인덱스를 잘라낸 결과를 파라미터로 재귀 호출을 수행한다.

- 재귀 호출이 계속되어 문자열의 길이가 계속 줄어든 결과, 문자열의 길이가 1 이하가 되면 해당 문자열은 회문 이라는 뜻이므로 true 를 반환한다.

- 만약 그렇지 않을 경우 false 를 반환한다.

 

다음번 글에서는 이 재귀호출을 이용해 백준에 있는 더 난이도 높은 문제들을 풀어보자.