[공부] 알고리즘 - Recursion 재귀

알림

본 글은 복습노트이며 권오흠님의 유튜브 알고리즘 강의를 보면서 공부한 후 공부한 내용을 정리하기 위한 것입니다!
초보자가 이해한 내용을 서술하는 것이기 때문에 내용에 크고 작은 오류가 있을 수 있습니다!
알고리즘 강의 유튜브 링크(https://www.youtube.com/channel/UC-cOmaeWLm7Ii7erMQNatvA)

시작

Recursion
되부름(재귀)
네이버 지식백과 IT 용어사전

주어진 문제를 해결하기 위해 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식. 어떤 루틴이나 프러시저가 자기 자신을 반복 호출하여 문제를 풀어 나가는 알고리즘으로, 이를 이용하기 위해서는 스택을 사용한다. 간단한 루틴을 풀 수 있는 반면 처리 속도가 느리고, 횟수가 지나치게 많으면 프로그램이 정지하기도 한다.

Recursion은 기본적으로 loop와 비슷하다. 함수가 자기자신을 호출해서 간단한 동작을 수행할 수 있도록 하는 것. 기능은 완전히 동일한 것으로 보이나 loop와는 달리 자기자신을 참조하는 것이기 때문에 사용하는 방법에서 약간의 차이가 있다. 이 부분을 이해하면 loop문을 통해 구현하기 어려운 로직을 recursion으로 구현할 수 있을 것 같다. (아직은 recursion에 대한 이해가 부족해서 가능할 것 같다는 감만 있을 뿐 방법은 모르겠다. 위의 생각이 맞는 생각인지도 아직은 확실치 않다.)

 

public class Code01 {

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

}

Recursion의 가장 기본적인 형식이다. 자세히 보면 functionA 메소드 내에 functionA 메소드를 호출하는 코드가 있다. 이 경우 프로그램을 실행시키면 어떤 일이 일어날까?

정답은 콘솔에 Hello가 무한히 찍힌다. functionA를 실행할 때마다 functionA 내에서 동일한 메소드가 계속해서 실행되기 때문에 프로그램을 절대 종료되지 않는다(물론 cpu를 보호하기 위해 프로그램이 강제로 종료될 수도 있다). 이런 경우, 흔히 loop문에서 사용하듯 함수 내에 조건을 걸어 무한회기를 방지할 수 있다.

 

public class Code02 {

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

위의 코드를 보면 functionB는 양의 정수 하나를 인자로 받고 함수가 한번 호출될 때마다 정수의 값을 하나씩을 낮춘다는 것을 알 수 있다. 그리고 정수가 계속해서 1씩 감소하다 0이 되면 functionB내의 조건문에 의해 함수는 종료된다.

functionB는 메소드가 끊임없이 되반복되는 functionA와는 다르게 브레이크 포인트가 있어 코드 작성자의 의도에 따라 원하는 만큼만 함수를 동작시키고 정지시킬 수 있다. 이 기능은 reculsion에서 매우 중요한데, 코드가 무한회기에 빠지지 않게 하기 위해서는 반드시 이러한 브레이크 포인트를 만들어줘야 한다. 일반적인 reculsion 함수에서는 위의 기능을 갖춘 장치가 (의도한 경우가 아니라면) 반드시 존재하며, 이런 기능을 base case라고 부른다.

 

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

위의 코드는 임의의 양의 정수값을 입력하면 1에서 시작해서 정수값까지의 합을 구해주는 프로그램을 구현한 것이다. 위의 식대로 프로그램을 실행하면 main 메소드에 의해 function(4)가 실행되고 function(4)는 함수 내에서 정수값이 0이 될 때까지 회기하게 된다. 그 결과는 다음과 같다.

 

흥미로운 지점은 값을 더해가는 과정이 4에서 시작해서 0으로 끝나는 것이 아니라(4+3+2+1+0), 0에서 시작해서 4로 끝나는 것이었다(0+1+2+3+4). 이는 추후에 문자열의 순서를 거꾸로 출력하는 함수를 만들 때 요긴하게 쓰일 개념이다. ("안녕하세요"를 출력하면 "요세하녕안"이 나오는 함수!)

 

public class Code05_Factorial {

	public static void main(String[] args) {
		int result = function(5);
		System.out.println(result);
	}
	public static int function(int n) {
		if (n <= 1) {
			return 1;
		} else {
			return n * function(n-1);
		}
	}

}

똑같은 방법으로 덧셈이 아니라 곱셈을 할 경우 n!이라고 표기할 수 있는 펙토리얼을 구할 수 있다. base case에서 return값이 0이 아닌 1인 것은 덧셈이 아니라 곱셈을 하기 때문이다. return값을 0으로 줄 경우 숫자로 무엇을 입력하든 값은 0이 나온다. (사실 return값이 0이 아닌 1인 이유는 0! = 1이기 때문이다.)

• n! = 1 x 2 x 3 x 4 x ... x (n-2) x (n-1) x n
• 0! = 1

 

public class Code06_Exponentiation {

	public static void main(String[] args) {
		int result = function(2, 10);
		System.out.println(result);
	}

	public static int function(int x, int n) {
		if (n == 0) {
			return 1;
		} else {
			return x * function(x, (n-1));
		}
	}

}

 

임의의 숫자의 임의의 제곱값을 구할 수 있는 프로그램이다. xⁿ을 구할 수 있는 것으로, 함수의 인자로 x와 n을 입력하면 해당 값이 나오게 된다. (인자가 하나 추가되었을 뿐이지 펙토리얼과 구조가 완전히 똑같다!)

 

public class Code07_Fibonacci {

	public static void main(String[] args) {
		int result = fibonacci(5);
		System.out.println(result);
	}
	
	// 1번째 = 1, 2번째 = 2. n번째는?
	public static int fibonacci(int n) {
		if (n < 3) {
			return n;
		} else {
			return fibonacci(n-1) + fibonacci(n-2);
		}
	}
}

다음은 피보나치 수열이다. 피보나치 수열은 n-2번째의 수열의 항과 n-1번째의 수열 항의 합이 n번째의 수열의 항과 같은 수열을 의미한다.

• 피보나치 수열 [ f_n = f_n-1 + f_n-2 ]
• 첫번째 항과 두번째 항은 각각 1, 2
• 혹은 0, 1 (둘중 어느거나 상관없다.)

이 피보나치 수열은 솔직히 애를 좀 먹었다. 예전에 배열을 이용해서 피보나치 수열을 만들었을 때 그때는 워낙 코드가 직관적이어서 이해가 굉장히 잘 됐지만 reculsion을 이용했을 때는 코드를 봐도 쉽지 않았다. 여기서 거의 30분은 있었던 것 같다.

 

그림까지 그려가며 이해하려 노력한 흔적

 

public class Code08_GreatestCommonDivisor {

	public static void main(String[] args) {
		int result = gcd(5040, 1155);
		System.out.println(result);
	}

	public static int gcd(int m, int n) {
		if (m < n) {
			int temp = m;
			m = n;
			n = temp; // m과 n의 값을 바꿈 (m을 더 크게 만들기 위함)
		}
		
		if (m % n == 0) {
			return n;
		} else {
			return gcd(n, m%n);
		}
	}
}

다음으로 또 어려웠던 코드. 인자 두 개의 최대공약수를 reculsion으로 도출하는 코드이다. 코드를 보자마자 머리가 멍.... 이것도 마찬가지로 30분정도 고민하며 들여다봤다. "최대공약수가 뭐였지?"부터 시작해서 "왜 n이랑 m과 n을 나눈 나머지를 인자로 넣지?"까지 머리 꽤나 썼던 코드... 솔직히 수학적인 부분에서는 아직도 이해가 안간다. 한참 코드랑 씨름하다가 노트에 최대공약수를 내는 공식을 검증하는 단계에까지 다다랐을 때, 문득 이렇게까지 최대공약수에 메달릴 이유가 있나 싶어서 포기했다. reculsion 개념에서 코드는 이해가 되었기 때문에 다음으로 넘어갔다.

 

public class Code09 {

	public static void main(String[] args) {
		int result = function("안녕하세요");
		System.out.println(result);
	}

	public static int function(String str) {
		if (str.equals("")) {
			return 0;
		} else {
			return 1 + function(str.substring(1));
		}
	}
}

다음으로 정수 말고 문자열 파트로 넘어가서 임의의 문자열을 입력했을 때, 그 문자열의 길이를 알려주는 코드이다. 문자열의 길이는 간단하게 'string.length()'로 얻으면 되지만 저 간단한 메소드를 직접 만들어보는게 재밌었다. 코드상에 length 메소드를 입력했을 때, 컴퓨터 단에서는 저런 프로세스를 거치면서 출력이 되는건가? 하는 생각을 했던 것 같다.

 

public class Code10 { 
	public static void main(String[] args) { 
    	System.out.println(printCharacters("안녕하세요")); 
    } 
    
    public static void printCharacters(String str) { 
    	if (str.length() == 0) { 
        	return; 
        } else { 
        	System.out.print(str.charAt(0)); 
            printCharacters(str.substring(1)); 
        }
    }

마지막으로 이 코드. 공부는 이것보다 더 많이 했었는데 복습하던 중 여기에서 탁 막혔다. 코드를 자세히 보면 사실 정상적인 코드가 아니다. 작동하지 않는 코드이다.

이 코드에서 한 20여분 씨름하면서 자바를 공부해야하겠구나 하는 생각을 절실히 느꼈다. 자바는 데이터타입에 되게 민감한 언어라고 하던데 과연 그렇구나, 생각했던 부분이었다. 알고리즘을 공부하면서 동시에 자바를 공부하려고 했었는데, 알고리즘 수업을 자바로 하니 자바 문법을 잘 몰랐을 경우에 진도가 막히는 애로사항이 있을 걸 생각하지 못했다. 내일은 자바를 공부해야겠다.

끝.

사설

국비지원 학원이 개강한지 1주일이 지났다. 선수학습까지 포함하면 9번의 수업을 들었고, 오늘은 1주차 토요일이다(12시가 넘어갔으니 일요일이구나). 국비지원 학원이 아직까지는 많이 널널한 편이라 개인적인 공부에 좀 박차를 가하고 있다. 아무래도 비전공자이고 cs지식도 전무한 편이라 스스로 이래저래 조금 많이 조급하고 불안한 것 같다. 6개월 과정의 교육이 지금 막 시작되었고 문득 지금처럼 너무 달리기만 하면 제풀에 지쳐 넘어질 수 있을 것 같다는 생각이 들어서 이렇게 공부기록 아닌 기록을 잠깐 남긴다. 급하게 앞만 보고 가지 말고 조금은 마음을 비우고 루즈하게 스스로를 챙기면서 공부를 하는 것도 좋을 것 같다. 파이팅!