210401. Today I Learned(TIL) : 재귀적 사고 복습

자바스크립트에서 재귀함수란, 더 이상 쪼갤 수 없을 때 까지 문제를 나눈 다음 가장 작은 단위의 값부터 차례대로 자기 자신 함수를 호출하여 값을 돌려주는 것을 말한다. 모든 재귀함수는 반복문으로 대체 가능하지만, 반복의 깊이가 어디까지 이어질지 알 수 없는 상황에서는 불필요한 코드를 줄이고, 보다 효과적으로 기능의 구현을 가능하게 한다는 장점이 있다.

가장 쉬운 예를 들어 재귀를 설명하자면 다음과 같다.
수를 요소로 가지는 배열 인자를 받고, 해당 배열의 요소들을 전부 더하는 함수 arrSum이 있다.
arrSum([1,2,3,4]) = 10 이다. 재귀를 이용하지 않고 반복문을 이용하면 코드는 다음과 같다.

function arrSum(arr) {
	let sum = 0;
    for(let i = 0; i < arr.length; i++) {
    	sum += arr[i];
        }
    	return sum;
     }
    
let input = [1,2,3,4];
console.log(arrSum(input)) = 10;

위와 같은기능을 구현하는 재귀함수를 만들어 보자.
arrSum([1,2,3,4])는 문제를 쪼개서 생각해보면 이렇다.

1 + arrSum([2,3,4])
1 + 2 + arrSum([3,4])
1 + 2 + 3 + arrSum([4])
1 + 2 + 3 + 4 + arrSum([])

이제 arrSum은 더 이상 쪼갤 수 없을만큼 작은 단위로 쪼개졌다. 이제 이 arrSum([])에 누적 덧셈에서 흔히 쓰는 초기값 0을 할당하자. 그럼 위의 식은 조금 바뀌게 된다.

arrSum([]) = 0
1 + arrSum([2,3,4]) = 1 + 9
1 + 2 + arrSum([3,4]) = 1 + 2 + 7
1 + 2 + 3 + arrSum([4]) = 1 + 2 + 3 + 4
1 + 2 + 3 + 4 + arrSum([]) = 1 + 2 + 3 + 4 + 0

arrSum([1,2,3,4]) = 10

이제 arrSum의 함수를 재귀로 표현해보자.

function arrSum(arr) {
const head = arr[0];
const tail = arr.slice(1);
	if(arr.length === 0) {
    	return  0;
     }
    else {
    	return head + arrSum(tail);
     }
  }  
    
let input = [1,2,3,4];
console.log(arrSum([input])) = 10;

arr의 0번째 인덱스 요소를 head라고 정의하고 arr를 앞에서부터 하나씩 요소를 자른 배열을 tail이라고 정의한 다음, 가장 최소단위인 빈 배열에 0이라는 값을 조건문으로 리턴할 수 있게 해준다. 그리고 최소단위에 이르기 전까지 입력받은 배열은 head + arrSum(tail)의 식을 반복한다. 반복문을 쓰지 않았음에도 불구하고 같은 식을 계속 반복하는 이유는 arrSum 함수가 함수 내에서 자기 자신을 호출하기 때문이다.

결론적으로 재귀는 반복문의 역할을 하지만 반복문보다 훨씬 간결하고 효율적이게 기능을 구현할 수 있게 한다. 재귀의 한 가지 단점은 반복을 중간에 멈출 수 없다는 것이다. 반복문은 멈추고 싶은 구간에 break를 걸어줄 수 있지만 재귀는 그럴 수 없다. 따라서 반복문과 재귀를 언제 어떻게 잘 활용할 수 있을지의 판단력은 다양한 케이스를 많이 경험해봄으로써 늘 것이다.
작자는 아직 코린이라 케이스를 많이 겪어보지 못했지만 앞으로 경험치를 쌓기 위해 노력할 것이다.