[알고리즘] 재귀 (Recursive)

고급 정렬 알고리즘에서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 익히는게 좋다.

 

1. 재귀용법 (recursive call, 재귀호출)

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

 

2. 팩토리얼 구하기

• 2! = 2 x 1
• 3! = 3 x 2 x 1
• 4! = 4 x 3 x 2 x 1
• n! = n x (n - 1)! 이라는 규칙이 보인다.

package Recursive;

public class Factorial {

	public static int factorial(int data) {
		if (data == 1) {
			return data;
		}	
		return data * factorial(data - 1);
	}
	public static void main(String[] args) {
		System.out.println("5! = " + factorial(5));
		System.out.println("4! = " + factorial(4));
		System.out.println("3! = " + factorial(3));
		System.out.println("2! = " + factorial(2));
	}
}

* 팩토리얼 시간복잡도와 공간복잡도

• factorial(n)은 n-1번의 factorial()함수를 호출한다. n-1번 반복문을 호출하는 것과 동일하므로 O(n)
• factorial()을 호출할때 마다 지역변수 n이 생긴다. 공간복잡도도 마찬가지로 O(n)

3. 재귀 호출과 스택

재귀 호출은 스택의 전형적인 예이다.

 

4. 회문 판별

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

ex : level, poop, abccba, abcdcba

package Recursive;

public class palindrome {
	
	public static boolean palindrome(String str) {
		if (str.length() <= 1) { // level -> eve -> v 길이가 1
			return true;
		} 
		
		if (str.charAt(str.length() - 1) == str.charAt(0)) {
			return palindrome(str.substring(1, str.length() - 1));
		} else {
			return false;
		}	
	}

	public static void main(String[] args) {
		String str1 = "level";
		String str2 = "cat";
		
		System.out.println("level은 " + palindrome(str1));
		System.out.println("cat은 " + palindrome(str2));
	}

}

 

5. 재귀 문제 프로그래밍 연습

Q. 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 

1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 로 총 7가지가 있다.

정수 n을 입력했을 때, n을 1,2,3의 합으로 나타낼 수 있는 방법의 수를 구하여라.

package Recursive;

import java.util.Scanner;

public class sunCase {
	
	public static int sumCase(int n) {
		if (n == 1)
			return 1;
		else if (n == 2)
			return 2;
		else if (n == 3)
			return 4;
		else {
			return sumCase(n - 1) + sumCase(n - 2) + sumCase(n - 3);
		}
		
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		System.out.println(sumCase(n));
	}

}