재귀(Recursion)
어떤 함수(혹은 프로시져, 서브 프로그램)에서 직접적으로 혹은 간접적으로 자기 자신 함수를 다시 호출하는 것.
무한 재귀에 빠지지 않도록 base case를 잘 정해주고, 반복되는 부분은 recursive step로 정의해준다.
Function call stack
프로그램 중 함수를 호출하면 (Context switching) 지금 실행중인 함수의 지역변수 등 가지고 있는 정보를 저장해두어야 한다. 그리고 새로운 함수 수행이 완료되면 다시 원래의 함수로 제어가 돌어오고, 기존의 정보를 복원해서 사용하여야 한다.
이때 현재 함수가 가지고 있던 정보를 저장하는 연속적인 메모리 공간을 activation record라고 하고, 이 activation record를 call stack 공간에서 관리한다.
함수를 호출하고 반환하는 과정이 last call first return 이므로, 함수의 activation record를 stack에 저장하는 것이 적합한 것이다. (stack -> Last in first out)
Linear sum
public static int sum(int[] arr, int n){
if(n==1) return arr[0];
else return sum(arr, n-1) + arr[n-1];
}
public static void main(String[] args) {
int[] arr = {3, 6, 5, 2, 4};
System.out.println(sum(arr, 5));
}n개의 정수가 주어졌을 때 그 정수의 합을 구한다.
Reversing array
public static void reverseArray(int[] arr, int lt, int rt){
if(lt>=rt) return;
else{
swap(arr, lt, rt);
reverseArray(arr, lt+1, rt-1);
}
}배열의 값 순서를 뒤집는다.
Fibonacci
public static int fibonacci(int n){
if(n<=1) return n;
else return fibonacci(n-2)+fibonacci(n-1);
}피보나치 수열의 n번째 항을 구한다.
이때 만약 작은 수를 다루는 경우라면 위의 예시처럼 단순한 재귀 구조를 활용해도 충분하다.
하지만 들어오는 수가 커진다면 문제가 생긴다.
만약 피보나치 수열의 2147483647번째 항을 구하고싶다면 어떻게 될까?
stackOverFlow 에러가 발생할 것이다.
이때 고려할 수 있는 방법은 행렬의 거듭제곱을 이용해 분할정복으로 문제를 푸는 것이다.
이 방법을 사용하면 O(2^n)이었던 피보나치 수열의 시간 복잡도를 O(log2 n)까지 개선할 수 있다.
위와 같은 과정을 통해 Fn과 관련된 식을 얻을 수 있다.
만약 n=3이라고 가정해보자.
그러면 이런 과정을 거치게 되므로, (1,0) 행렬식을 굳이 곱해서 구하지 않아도 Fn을 알아낼 수 있게 된다.
(1, 1) (1, 0)행렬을 n-1번 곱한 것의 제일 앞 원소가 Fn이 되는 것이다. 이것을 코드로 반영하면 아래와 같다.
public class RapidFibonacci {
static int[][] unit = {{1, 1}, {1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(fibonacci(n));
}
public static long fibonacci(long n) {
if (n <= 1) {
return n;
}
int[][] result = pow(unit, n - 1);
// unit에 n-1제곱을 한 것의 제일 앞 원소가 우리가 구하는 Fn이다.
return result[0][0];
}
public static int[][] pow(int[][] a, long n) { //행렬의 제곱
if (n == 1) {
return a;
}
//제곱으로 곱해지는 수가 짝수인지 홀수인지 모르므로 케이스를 나눠 처리한다.
int[][] half = pow(a, n / 2);
if (n % 2 == 0) {
return multiply(half, half);
} else {
return multiply(multiply(half, half), unit);
}
}
public static int[][] multiply(int[][] a, int[][] b) { //행렬끼리의 곱셈
int[][] result = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
// 자료형의 범위를 넘어가기 때문에 마지막 세자리수만 출력하도록 처리한다.
result[i][j] = (result[i][j] + a[i][k] * b[k][j] % 1000) %1000;
}
}
}
return result;
}
}
최대 공약수 (유클리드 호제법)
public static int euclid(int a, int b){
if(b==0) return a;
else return euclid(b, a%b);
}유클리드 알고리즘을 이용해 최대 공약수를 구한다.
팰린드롬 검사(palindrome)
public static int palindrome(char[] arr, int lt, int rt){
if(lt>=rt) return 1; //팰린드롬이 맞으면 1을 리턴
else if(arr[lt] != arr[rt]) return 0; //아니면 0을 리턴
else return palindrome(arr, lt+1, rt-1);
}주어진 문자열이 대칭인 글자인지 확인한다.
팰린드롬이 맞으면 1, 아니면 0을 리턴한다.
진수변환
public class BaseConversion {
public static void baseConversion(int n, int base){
String[] baseTable = "0123456789abcdef".split("");
if(n>base) baseConversion(n/base, base);
System.out.print(baseTable[n % base]);
}
public static void main(String[] args) {
int num = 123;
baseConversion(123, 8);
}
}주어진 십진수의 정수를 다른 진수의 숫자로 변환한다.
변환되는 진수의 기수는 2~16의 범위를 가진다.
순열(Permutation)
public class Permutation {
static String[] pm;
static int[] ch;
public static void permutation(int L, int n, String[] arr){
if(L==n){
for (String s : pm) {
System.out.print(s);
}
System.out.println();
}
else{
for (int i = 0; i < arr.length; i++) {
if(ch[i]==0){
ch[i] = 1;
pm[L] = arr[i];
permutation(L+1, n, arr);
ch[i] = 0;
}
}
}
}
public static void main(String[] args) {
String str = "abc";
String[] strArr = str.split("");
pm = new String[str.length()];
ch = new int[str.length()];
permutation(0, str.length(), strArr);
}
}주어진 스트링의 문자를 가지고 사전순 문자열 순열을 생성하는 알고리즘이다.
ch 배열을 통해 사용했는지, 사용하지 않았는지를 표시해두며 재귀를 돌도록 한다.