[알고리즘] 순환(Recursion)의 개념과 기본 예제 1

인프런 무료 강의 권오흠교수님 '영리한 프로그래밍을 위한 알고리즘 강좌' 보면서 공부한 내용입니다.
부족한 내용이나 잘못된 내용은 댓글남겨주시면 감사하겠습니다!

출처 : https://inf.run/iezc

자기 자신을 참조하는 재귀함수의 순환에 대해 3일에 나눠서 학습할 예정이다.

먼저, 처음에는 아무런 조건을 주지 않은 상태에서 순환함수를 생성해보았다.

/*
 * 순환(Recursion)의 개념과 기본 예제 1-01
 * -> 무한 루프 발생
 */
package edu.recursion;

public class Recursion01_01 {
	public static void main(String[] args) {
		func();
	}
	
	public static void func(){
		System.out.println("Hello....");
		func();
	}
}

이렇게 아무런 조건 없이 자기 자신을 호출하는 재귀함수를 사용할 경우 무한 루프에 빠지게 된다.

 

다음 사진처럼 결국 무한루프에 벗어나지 못해 오류가 나는 모습을 볼 수 있다.

 

 

그럼 순환함수는 무조건 무한루프에 빠지게 되는 것 일까?

그럼 순환함수를 쓰는 의미가 없을 것이다.

이제부터 순환함수를 제대로 쓰는 법에 대해서 알아보자.

/*
 * 순환(Recursion)의 개념과 기본 예제 1-02
 * 	조건을 걸어줄 경우 무한루프 발생하지 않음
 * 	-> Hello.... 4번 출력
 */
package edu.recursion;

public class Recursion01_02 {
	public static void main(String[] args) {
		func(4);
	}
	
	public static void func(int n){
		// Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함
		if(n<=0){
			return;
		}
		// Recursive case : recursion을 반복하다보면 결국 base case로 수렴해야 함
		else{
			System.out.println("Hello....");
			func(n-1);
		}
	}
}

 

이렇게 Base case, Recursive case를 설정할 경우 무한루프에 빠지지 않고 재귀함수를 원하는 대로 잘 쓸 수가 있다.

재귀함수를 쓰는 순간 무한루프에 빠질 수 있기 때문에 탈출 할 수 있는 경우인 Base case를 적어주고 재귀함수를 호출 할 Recursive case를 써주면 된다.

 

이제부터 재귀함수, 즉 순환함수를 활용한 다양한 수학계산을 해보자.

다음은 0~n까지의 합을 구하는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 1-03
 * 	1-n까지의 합 구함 
 * 	-> 10
 * 
 * [ 순환함수와 수학적귀납법 ]
 * func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 계산
 * 
 * # 증명
 * 1. n=0인 경우 : n=0인 경우 0을 반환 -> 올바름
 * 2. 임의의 양의 정수 k에 대해서 n<k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정
 * 3. n=k인 경우 고려. func은 먼저 func(k-1)호출하는데 2번의 가정에 의해서 0에서 k-1까지의 합이 올바로 계산되어 반환
 * 	   메서드 func은 그 값에 n을 더해서 반환.
 * 	   따라서 메서드 func은 0에서 k까지의 합을 올바르게 계산하여 반환
 */
package edu.recursion;

public class Recursion01_03 {
	public static void main(String[] args) {
		int result = func(4);
		System.out.println(result);
	}
	
	// 0~n까지의 합을 구하는 함수
	public static int func(int n){
		if(n<=0){
			return 0; // n=0일 경우 합은 0
		}
		else{
			// n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것
			return n+func(n-1);
		}
	}
}

0~4까지의 합은 잘 알다싶이 10이다. main에서 func의 매개변수에 4를 넣어서 호출하는 순간,

func함수는 매개변수의 4가 0보다 큰지 비교를 한 후 0을 제외한 양수일 경우 현재 값인 4에 1을 뺸 3을 호출하고 4를 더해준다.

이렇게 반복을 하다보면 4+3+2+1+0이 되고 10이 출력하게 된다.

 

중, 고등학교 때 많이 공부했던 Factorial도 순환함수를 사용해서 구할 수 있다.

/*
 * 순환(Recursion)의 개념과 기본 예제 1-04
 * 	Factorial : n!
 * 	-> 11
 * 
 * [ Factorial ]
 * 0! = 1
 * n! = nx(n-1) 	n>0
 * 
 * [ 순환함수와 수학적귀납법 ]
 * factorial(int n)은 음이 아닌 정수 n에 대해서 n!을 계산
 * 
 * # 증명
 * 1. n=0인 경우 : n=0인 경우 1을 반환 -> 올바름
 * 2. 임의의 양의 정수 k에 대해서 n<k인 경우 n!을 올바르게 계산한다고 가정
 * 3. n=k인 경우 고려. 
 * 	   factorial은 먼저 factorial(k-1)호출하는데 2번의 가정에 의해서 (k-1)!이 올바로 계산되어 반환
 * 	   따라서 메서드 factorial은 k*(k-1)! = k!을 반환
 */
package edu.recursion;

public class Recursion01_04 {
	public static void main(String[] args) {
		int result = factorial(4);
		System.out.println(result);
	}
	
	public static int factorial(int n){
		if(n==0){
			return 1; 
		}
		else{
			return n+factorial(n-1);
		}
	}
}

교수님의 설명을 코드에 주석으로 달아놨고, 원리는 위와 동일하니 설명은 생략하겠다.

 

x의 승을 구하는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 1-05
 * 	x^n
 * 	-> 16.0
 * 
 * [ x^n ]
 * x^0 = 1
 * x^n = x*x^n-1 	if n>0
 * 
 */
package edu.recursion;

public class Recursion01_05 {
	public static void main(String[] args) {
		double result = power(2, 4);
		System.out.println(result);
	}
	
	public static double power(double x, int n){
		if(n==0){
			return 1; 
		}
		else{
			return x*power(x, n-1);
		}
	}
}

 

다음은 피보나치 수를 구하는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 1-06
 * fibonacci numbers - 피보나치 수
 * 	-> 3
 * 
 * [ 피보나치 수]
 * f0 = 0
 * f1 = 1
 * fn = fn-1 + fn-2		n>1
 * 
 */
package edu.recursion;

public class Recursion01_06 {
	public static void main(String[] args) {
		int result = fibonacci(4);
		System.out.println(result);
	}
	
	public static int fibonacci(int n){
		if(n<2){
			return n; 
		}
		else{
			return fibonacci(n-1) + fibonacci(n-2);
		}
	}
}

 

마지막은 최대공약수를 구하는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 1-07
 * Euclid Method 최대공약수
 * 	-> 2.0
 * 
 * m >= n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n) =n이고, 
 * 그렇지 않으면 gcd(m, n) = gcd(n, m%n)이다.
 * 
 */
package edu.recursion;

public class Recursion01_07 {
	public static void main(String[] args) {
		double result = gcd(2,4);
		System.out.println(result);
	}
	
	public static double gcd(int m, int n){
		if(m<n){
			// swap m and n
			int tmp =m;
			m =n;
			n =tmp;
		}
		if(m%n == 0){
			return n;
		}
		else{
			return gcd(n, m%n);
		}
	}
}

 

교수님꼐서 설명을 너무 잘해주셔서 이해하는데 크게 어려움은 없었다. 

일단 알고리즘을 공부해야겠다고 생각은 들었는데 어떻게 시작을 해야할지 모를 경우, 아직 문제풀이를 할 자신이 없고 설명을 먼저 듣고 싶을 경우 이 강의를 추천한다.

 

특별한 일이 없을 경우 일주일에 3일씩 강의를 듣고 포스팅을 할 예정이다.