[알고리즘] 순환(Recursion) 01

순환(Recursion)

인프론 강의를 보면서 연습하고 기록하고 있습니다

0에서 n까지 합

public class Test {
	public static void main(String[] args) {
		int result = func(4);
		System.out.println("0에서 n까지의 합 : " + result);
	}

	public static int func (int n) {
		if(n==0) {
			return 0;
		}else {
			return n + func(n-1);
		}
	}
}

0에서 n까지의 합 : 10

Factorial n!

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

public class Test {
	public static void main(String[] args) {
		int result = factorial(4);
		System.out.println("4! = " + result);
	}

	public static int factorial (int n) {
		if(n==0) {
			return 1;
		}else {
			int print = n * factorial(n-1);
			System.out.println(n + " , " + print);
			return print;
		}
	}
}

1 , 1
2 , 2
3 , 6
4 , 24
4! = 24

xⁿ

x^0 = 1
xⁿ = x*xⁿ-¹ if n>0

public class Test {
	public static void main(String[] args) {
		double result = power(2, 6);
		System.out.println("2^6 = " + result);

	}

	public static double power (double x, int n) {
		if(n==0) {
			return 1;
		}else {
			double print = x * power(x, n-1);
			System.out.println(n +" , " + print);
			return print;

		}
	}
}

1 , 2.0
2 , 4.0
3 , 8.0
4 , 16.0
5 , 32.0
6 , 64.0
2^6 = 64.0

Fibonacci Number

피보나치는 수열 종류 중 하나

1 1 2 3 5 8 13 21 34….

앞에 있는 숫자와 그 앞에 있는 숫자와 더한 것을 나열하는 것.

1+1 = 2
2+3 = 5
3+5 = 8
5+8 = 13

f0 = 0
f₁ = 1
fn = fn-₁ + fn-₂ n>1

public class Test {
	public static void main(String[] args) {
		int input = 6; //6번째
		for(int i=1; i<=input; i++) {
			System.out.println(fibonacci(i));
		}
	}

	public static int fibonacci (int n) {
		if(n<2) {
			return n;
		}else {
			return fibonacci(n-1) + fibonacci(n-2);
		}
	}
}

1
1
2
3
5
8

최대공약수 : Euclid Method

public class Test {
	public static void main(String[] args) {
		System.out.println("최대공약수 : "+gcd(12,9));
	}

	public static int gcd (int m, int n) {
		if(m<n) {
			int tmp = m;
			m = n;
			n = tmp;
		}

		if(m%n==0) {
			//m이 n의 배수이면 gcd(m,n)=n
			return n;
		}else {
			System.out.printf("%d, %d %n" , n, m%n);
			// gcd(m,n) = gcd(n,m%n)
			return gcd(n , m%n);
		}
	}
}

9, 3
최대공약수 : 3

최대공약수 : Euclid Method 간단 버전

//최대공약수 : Euclid Method 간단 버전
public class Test {
	public static void main(String[] args) {
		System.out.println("최대공약수 : "+gcd(9,12));
	}

	public static int gcd (int m, int n) {
		if(n==0) {
			return m;
		}else {
			System.out.printf("%d, %d %n" , n, m%n);
			return gcd(n , m%n);
		}
	}
}

12, 9
9, 3
3, 0
최대공약수 : 3