봄이네집의 일고리즘 - 1) 재귀함수 1강, 재귀란 무엇인가

사실 저는 알고리즘을 잘 못합니다.

잘 하면 이걸 왜 공부하겠어요? 잘 못하니까 하는 것이지요.
알고리즘 학습의 중요성에 대해서는 사실 현업에 계신 분들 사이에서도 의견이 자주 갈리고는 합니다. 필요성을 느낄 때까지는 학습을 미뤄도 된다는 분들도 있고, 프로그래밍을 시작할 때부터 공부를 꾸준히 해야한다는 분도 있습니다.

접근 방식에도 의견이 많이 갈립니다.

“컴퓨터 공학” 의 한 주제로 학습해야 한다고 주장하는 분들도 있고, 프로그래밍 로직을 학습하며 공부해야 한다고 말씀하시는 분들도 있습니다.

어쨌거나 이걸 잘 해야 코딩테스트를 볼 수 있습니다.

네….취업해야죠…..

알고리즘을 취업의 수단 으로 생각하는 것에 대해 우려의 목소리가 있는 것도 사실입니다. 더군다나 요즘 업계의 대기업들이 경쟁적으로 블라인드 코딩 테스트를 도입하면서, 창의적으로 자신의 생각을 코드로 펼쳐낸다는 알고리즘의 본래 취지와는 달리 이른바 “먹히는 코드”, “뚫리는 코드” 가 족보처럼 인터넷에서 공유되며 암기와 반복 숙달이 횡행하고 있는 것이 사실입니다.

저는 취업만을 위해 알고리즘 공부를 하고싶지는 않습니다.

사실 저는 알고리즘이 신입 개발자의 필수 역량이라고 생각하지 않고, 대기업 취업이 전부라고도 생각하지 않습니다. 오히려 제가 정말 좋아하고 관심있어하는 분야의 사업을 하는 스타트업이나 작은 회사에 들어가 신나게 개발하며 역량을 쌓다가 더 큰 회사로 옮기는 시나리오를 꿈꿉니다.

제가 생각하는 이상적인 알고리즘 공부란 이렇습니다. 내가 컴퓨터와 조금이라도 더 가까워질 수 있게 해 주는 공부. 소위 “컴퓨터적인 사고” 를 능숙하게 구사할 수 있도록 도와주는 알고리즘 공부를 해 보고 싶습니다.

또한 실제 코드에의 적용을 통한 클린 코드 구현 및 최적화를 경험해보고 싶습니다. 실제로 배운 정렬 알고리즘이나 탐색 알고리즘을 통해 코드 실행시간을 줄이고, 깔끔한 코드 작성을 할 수 있다면, 알고리즘 공부를 즐기게 되지 않을까요?

그래서 오늘부터 시작합니다. 봄이네집의 일고리즘(1일 1 알고리즘).

---

알고리즘 (1) 재귀함수에 대하여.

재귀함수는 자기 자신을 한 번 더 호출하는 함수를 말합니다. 자기 자신을 다시 호출하며 반복 작업을 수행하고, 이를 통해 결과를 도출하는 것이죠. 예를 들면 이런 거죠.

어느날 학생이 선생님에게 물었습니다. “선생님, 재귀함수가 뭔가요?”
선생님이 답했습니다.
“학생, 예전에도 내게 똑같은 질문을 한 학생이 있었다네. 그 학생도 오늘 자네처럼 내 연구실에 찾아와서 나에게 물었어.”

“선생님, 재귀함수가 뭔가요?”

“학생, 예전에도 내게 똑같은 질문을 한 학생이 있었다네. 그 학생도 오늘 자네처럼….”

이 학생은 아마 종강할때까지 답을 얻지 못할 겁니다. 이 재귀함수는 무한 루프에 빠졌거든요.

감이 좀 오시나요? 재귀함수는 이처럼 자기 자신을 다시 호출하며 정해진 답을 도출해내는 과정을 구현합니다.

Base Case의 구현

학생은 교수님에게 재귀함수에 대한 따뜻한 말 한마디 듣고 싶었지만 교수님은 종강할 때까지 그에게 답을 주지 못했습니다.

왜 그랬을까요? 교수님의 재귀함수는 적절한 base case를 갖지 못했기 때문입니다.

Base case란 재귀 호출에 빠지거나, 재귀 호출을 일으키지 않는 재귀함수의 기본 케이스를 말합니다. 예제를 통해 살펴보죠.

우리는 다음 예제에서 “hello world”를 다섯 번 표시하는 재귀함수를 만들 겁니다. 어느 쪽이 base case인지 잘 살펴보세요.

....
int repeat = 5;

public void HelloRecursion(){
	
	if (repeat == 0){
		return;
	}

	else{
		System.out.println("hello world!");
		repeat--;
		HelloRecursion();
	}
}

이 코드를 통해 우리는 화면에 hello world를 다섯 번 출력했습니다. 출력이 반복될 횟수는 전역 변수 repeat을 통해 5회로 정의했습니다.

재귀함수 HelloRecursion()이 호출되면 가장 먼저 repeat의 값을 확인합니다. 만약 repeat이 0이라면 우리는 더 이상 hello world를 출력하지 않고 return;을 통해 이 재귀함수의 재귀 호출을 끝낼 것입니다.

만약 0이 아니라면요? 좀 더 일해야 합니다. System.out.println(“hello world”)를 통해 화면에 메아리 없는 안녕을 찍어준 다음, 저장되어 있는 repeat 값을 하나 깎고 자기 자신을 다시 호출할 것입니다.

만약 repeat값이 0까지 깎인다면, 앞서 살펴본 바와 같이 이 메소드는 종료됩니다. 이처럼 재귀 호출을 일으키지 않고 함수를 끝내거나 결과값을 돌려주는, 재귀 함수의 가장 기본이 되는 케이스를 base case라고 합니다.

모든 재귀함수는 base case를 가져야 합니다.

없으면요? 프로그램이 종료되지 않습니다. 어리둥절한 당신을 괴문자가 가득 찍혀있는 콘솔이 반겨줄 것입니다. 물론 의미있는 결과값도 얻을 수 없겠죠.

재귀함수를 구상할 때 가장 먼저 고민해야 할 것은 base case의 구현입니다. 이 함수가 어떤 조건에서 다음 재귀호출을 진행하지 않고 결과값을 돌려줄 것인지를 결정해야 합니다.

다음은 0부터 N까지의 자연수의 합을 구하는 재귀함수입니다.

...

public static int Sum(int n){
	
	if (n == 0){
		return n;
	}

	else{
		return n + Sum(n - 1);
	}
}

이 재귀함수는 자연수 n과 n - 1 을 파라메터로 재귀호출한 값의 합을 리턴합니다. 단 n이 0이 되면 더이상 재귀호출은 일어나지 않습니다. 이처럼 재귀함수에선 base case를 구현해야 재귀함수가 무한 루프에 빠지지 않습니다.

정리

재귀함수의 기본 개념과 간단한 예제를 살펴보았습니다. 우선 재귀함수는 자기 자신을 다시 호출하는 함수임을 배웠습니다. 또한재귀호출을 진행하지 않는 base case가 존재한다는 걸 배웠습니다. base case 없이 재귀함수는 무한루프에 빠진다는 것 또한 알게 됐습니다(가능하면 base case 없는 재귀함수를 통해 무한루프에 한 번 빠져 보시기를 권장합니다.) .

재귀함수로 풀 수 있는 유명한 문제가 몇 가지 있습니다. 두 수의 최대공약수를 구하는 유클리드 호제법 과 피보나치 수열, 팩토리얼 계산 등이 그것입니다. 이 세 문제들은 재귀함수를 처음 학습할 때 가벼운 마음으로(?) 접근해볼 수 있는 주제들입니다.

처음부터 거창한 로직을 짜려고 끙끙대지 말고, base case의 구현부터 고민해 보세요. 어떤 순간에 이 함수가 재귀 호출을 끝내고 결과값을 돌려줄지 결정하고 나서, 어떻게 다음 로직(recursive case라고 합니다)을 구현할 지 결정하는 겁니다.

“알고리즘” 이라는 거창한 개념의 복잡성과 달리 재귀함수는 재밌게, 가볍게 학습할 수 있는 주제입니다. 여러분의 행복한 알고리즘 학습을 응원합니다!

오늘 학습에 사용된 코드는 제 깃헙 리포지토리에 모두 게시되어 있습니다.