[알고리즘] 재귀 접근 방법이란? | 자기 자신을 호출하는 함수 재귀함수

 

재귀라는게 말로는 쉬운데 깊이 이해하기가 참 어려운 것 같다.

그래서 포스팅좀 해볼라고...

 

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...

---

재귀함수(再歸函數)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.

 

재귀는 큰 문제의 풀이법을 작은 문제의 같은 풀이법으로 구성할 수 있을 때 사용되는 문제 해결 기법이다.

 

재귀를 사용할 때는 다음 사항을 주의해야 한다.

 

1. 재귀에는 항상 종료 조건이 있어야 한다. 종료 조건이 없다면 재귀 호출을 무한반복하게 된다.

2. 재귀 함수는 전체 작업의 일부만 수행하고 나머지는 재귀 호출에 위임한다.

 

재귀 방식으로 문제를 해결하는 과정은 생각만큼 어렵지 않다. 오히려 대부분의 경우 전체 문제를 한 번에 풀지 않아도 되므로 상대적으로 더 쉽다.

 

재귀 함수의 코드는 다음의 두 부분으로 구성된다.

 

1. 더 큰 범위의 풀이법을 같은 형태지만 더 작은 범위의 인수를 가진 풀이법을 사용해 정의하여 구체화하기

2. 종료 조건을 지정하기

 

Example : 1에서 n까지 양의 정수의 합을 계산하기

 

function sum(n) {

	if(n <= 0) {
		return 0;
	} 
	else if (n == 1) {
		return 1;
	}
	else {

		if(n > 100) {
			return;
		}
		else {
			return n  + sum(n-1);
		}
		
	}
}
console.log(sum(50))

 

이 코드는 다음과 같이 더 짧게 고쳐 쓸 수 있다.

 

function sum(n) {

	return (n<=0) ? 0 : ((n==1) ? 1 : (n+sum(n-1)));
}
console.log(sum(50))

 

쉬운 코드와 복잡한 코드 중에 선택을 해야한다면, 성능이나 메모리의 이점이 있지 않은한 쉬운 코드가 좋다.

 

이 기준은 코딩 면접을 위한 것만이 아니다. 작성된 코드는 팀 내 여러 사람이 읽어야 하므로 쉬운 코드가 더 좋다.

코딩 면접에서 코드를 짧게 작성할 때의 한 가지 확실한 이점은 종이에 빈 공간이 더 많이 남기 때문에 실수를 했을 때 수정할 수 있는 여백이 생긴다는 것이다.

 

※ 재귀는 종료조건을 누락하면 안된다. 종료 조건을 누락하면 재귀 홰출이 무한히 반복될 수 있다.

 

 

연습문제 1-1

계승(factorial)함수는 모든 음이 아닌 정수에 대해 다음과 같이 재귀 방식으로 정의할 수 있다.

 

fact(n) = n * fact(n-1), if n > 1 = 1, if n = 1

 

int n을 인수로 받아 n의 계승을 반환하는 함수를, 재귀를 사용하는 방식과 사용하지 않는 방식 두 가지로 작성해보자.

 

function factorial(n) {
	if(n <= 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	else {
		return n * factorial(n-1);	
	}
}

console.log(factorial(20))

function factorial2(n) {

	let sum = 1;

	if(n <= 0) {
		return 0;
	}
	else if (n == 1) {
		return 1;
	}
	else {
		for(var i = 1; i <= n; ++i) {
			sum = sum * i;
		}

		return sum;
	}
}

console.log(factorial2(20))

 

연습문제 1-2

 

정수 값의 배열이 주어졌을 때 배열의 각 원소를 누적합으로 갱신하는 재귀 함수를 작성해봅시다.

예를 들어 입력 배열이 다음과 같다고 합시다.

 

[1,2,3,4,5,6]

그러면 이 함수는 배열을 다음과 같이 갱신해야 합니다.

[1,3,6,10,15,21]

 

var arr = [1,2,3,4,5,6];
var arr2 = [];

function factorial(x) {
  if (x<0) return;
  if (x===1) return 1;
  return x + factorial(x-1);
}

function main() {

	for(var i = 1; i<=arr.length; i++) {
		console.log(i)
		arr2.push(factorial(i));
	}
	return arr2;
}

console.log(main())

위 코드가 맞는지는 모르겠지만 별것도 아닌게 머리 아프게 하고 있다 진짜 허허;;