[알고리즘] 재귀 문제 풀이(백준 27433번, 10870번, 25501번)

1. 팩토리얼2(백준 27433번 문제)

 

27433번: 팩토리얼 2 (acmicpc.net)

27433번: 팩토리얼 2

 

▷ 풀이 코드

import java.util.Scanner;

public class Factorial_backjoon {
	static long factorial(long n) {
		if(n > 0) {
			return n * factorial(n-1);
		} else {
			return 1;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long n = sc.nextLong();
		
		System.out.println(factorial(n));
	}
}

 

 

 

2. 피보나치 수5(백준 10870번 문제)

 

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

▷ 풀이 코드

import java.util.Scanner;

public class Fibonacci_backjoon2 {
	static long fibonacci(long n) {
		if(n > 1) return fibonacci(n-1) +  fibonacci(n-2);	
		else if(n == 1) return 1;
		else return 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long n = sc.nextLong();
		
		System.out.println(fibonacci(n));
	}
}

 

 

 

3. 재귀의 귀재(백준 25501번 문제)

 

25501번: 재귀의 귀재 (acmicpc.net)

25501번: 재귀의 귀재

 

▷ 풀이 코드

import java.util.Scanner;

public class Palindrome_backjoon3 {
	static int cnt;
	
	static int palindrome(String a, int x, int y) {
		cnt++;
		if(x >= y) return 1;
		else if(a.charAt(x) != a.charAt(y)) return 0;
		else return palindrome(a, x+1, y-1);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		for(int i=0; i<n; i++) {
			String a = sc.next();
			System.out.println(palindrome(a, 0, a.length()-1) + " " + cnt);
			cnt = 0;
		}
	}
}

 

 

이번에는 알고리즘 스터디를 통해 재귀 함수에 대해서 공부했습니다!

재귀란 어떤 사건에 자기 자신을 포함하고나 자기 자신을 사용해 정의하는 것입니다.

 

사용하는 이유는 무한으로 루프를 돌려서 결과를 출력할 때 사용합니다.

 

간단한 예시로는 위에서 풀어보았던 팩토리얼, 피보나치수열 등이 있죠!

 

팩토리얼에서 곱셈을 덧셈으로 변경하면 해당 숫자까지의 합을 구할 수 있겠어요!!

 

간단한 예시를 하나 볼까요?

 

재귀의 사용방법 및 출력 순서는 아래와 같습니다.

import java.util.Scanner;

public class Recur {
	static void recur(int n) {
		if(n > 0) {
			recur(n-1);
			System.out.println(n);
			recur(n-2);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
				
		System.out.print("정수를 입력하세요 : ");
		int n = sc.nextInt();
		
		recur(n);
	}
}

코드를 순서대로 진행하면 아래와 같이 recur 함수 안에 recur 함수를 자꾸 파고들어가며 n이 0보다 큰 조건이 될때까지 반복합니다.

이렇게 찾으면서 실행되는 순서는 표기한대로 1→2→3→4→5→6→7의 순서로 진행됩니다.

출력 값은 1231421이 출력되며 재귀가 어떻게 진행되는지 알 수 있습니다!

 

재귀 방식도 마찬가지로 코딩테스트할 때 많이 사용된다고 하네요~

 

다양한 문제들을 많이 풀어봐야 익숙해질 것 같네요!

 

다음 스터디때는 재귀의 응용 방법에 대해서 배워볼게요!

 

많은 분들의 피드백은 언제나 환영합니다!  많은 댓글 부탁드려요~~