11 재귀적으로 작성하는 법

재귀 카테고리

재귀문제에는 다양한 카테고리가 있다 .

어떤 카테고리에 효과적인 기법을 터득하는 것이 좋다.

1. 반복실행

숫자 출력 작업을 반복적으로 실행한다.

function countdown(number){
	console.log(number);
	
	if(number === 0){ number가 0일때가 기저조건
	return;
	}else{
		countdown(number-1);
	}

}

함수의 마지막 줄에서 단순히 그 함수를 다시 한 번 호출했다.

1-1 재귀트릭: 추가인자 넘기기

한 작업을 반복적으로 실행하는 카테고리

• 제자리수정
  • 실제함수에 전달된 원본배열을 바꾼다는 뜻

function double_array(array, index){
	array[index] *= 2
	double_array(array, index +1)
}

배열 외에 기록할 인덱스까지 인수로 받고

연속적인 재귀호출마다 인덱스를 증가시키고 기록한다.

보완한방법

function double_array(array, index){
	//기저조건: 인덱스가 배열 끝을 지날 떄 
	if(index >= array.length ){
		return
	}
	array[index] *= 2
	double_array(array, index +1)
}

인수의 기본값을 할당해서

함수를 처음 호출할 때 인덱스 인자를 전달하지 않아도 되도록 했다.

2. 계산

하위문제의 계산결과에 기반해 계산할 수 있을 때 재귀가 유용하게 쓰인다.

6의 계승을 구하는 문제 = 1x2x3x4x5x6

function factorial(number){
		if (number == 1){
			return 1
		}else{
			return number * factorial(number-1)
		}

}

하위문제에 기반해 계승을 계산하면된다.

factorial(5)에 6을 곱한 값이 결과이므로

factorial(5)는 factorial(6)의 하위문제이다.

2-1 두가지 계산방식

계산함수를 작성하는 방식은 상향식과 하향식이 있다.

상향식전략은 인자를 추가로 전달하는 방법을 써야한다.

function factorial(n, i=1, product=1){
		if(i>n){
			return product
		}
		return factorial(n, i+1, product * i)
}

그다지 간결하지 못하며 전형적인 루프에 비해 장점이 없다.

상향식에서는 루프와 재귀의 계산방식이 같다.

3. 하양식 재귀: 새로운방식

재귀는 하향식 재귀방식을 구현하는데 탁월하다.

하향식 사고방식은 문제를 해결하는 새로운 사고전략을 제공한다.

3-1 하향식 사고절차

1. 작성중인 함수를 이미 누군가 구현해놨다고 상상한다.
2. 문제의 하위문제를 찾는다.
3. 하위문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작한다.

3-2 배열 합

const array= [1,2,3,4,5]

array를 모두 합하는 sum 함수를 작성한다고 쳤을 때
sum함수가 이미 구현되어있다고 가정하고 하위문제를 찾는다. 

하위문제는 첫번째 원소를 제외한 배열 내 모든 수이다.
[2,3,4,5]

문제를 풀려면 첫번째 원소를 더하면 된다.
sum([2,3,4,5])+ array[0] 

끝으로 기저조건을 처리한다.
function sum(array) {
    // 기저 조건: 빈 배열이면 합은 0
    if (array.length === 0) {
        return 0;
    }
    
    // 배열의 첫 번째 요소와 나머지 요소로 분리하여 합산
    return array[0] + sum(array.slice(1));
}