알고리즘 재귀함수 문제(프로그래머스 Lv1. 삼총사)

모든 재귀함수 반복문은 while 또는 for 반복문으로 표현할 수 있다.
하지만 반복문이 너무 깊어지면 가독성이 안좋고 이해하기 어렵다.(현재는 재귀가 이해하기가 더 어렵지만 ..)

반복문을 작성하기는 쉬운데 재귀함수로 작성하는 것은 정말 어렵다.
코딩테스트 문제를 재귀함수로 작성한 풀이를 보며 연습해보자.
프로그래머스의 삼총사 문제를 푸는데 첫번째 트라이에는 삼중for문밖에 생각이 나지 않았다ㅎㅎ

 

function solution(number) {
    let result = 0;

    const combination = (current, start) => {
        if (current.length === 3) {
            result += current.reduce((acc, cur) => acc + cur, 0) === 0 ? 1 : 0;
            return;
        }

        for (let i = start; i < number.length; i++) {
            combination([...current, number[i]], i + 1);
        }
    }
    combination([], 0);
    return result;
}

 

combination([], 0); 에서 시작한다. 

combination은 삼중포문과 같이 모든 경우의 수로 숫자를 조합한다. 재귀를 돌며 바로 다음 인덱스의 숫자를 담고, if문에서 길이가 3이면 합을 평가하고 재귀를 종료하기 때문에 3개의 숫자들만 조합된다. if문에서 합이 0이면 result변수에 1을 더하고, 모든 재귀를 마치면 result변수를 반환한다.
combination에 start변수를 전달해주며 이미 담긴 요소의 다음 인덱스부터 재귀를 돌 수 있다.

 

삼총사 문제 재귀함수 풀이
combination([], 0)	시작
combination([ number[0] ] , 1)	i(1)=0
combination([ number[0], number[1] ] , 2)	i(1)=0, i(2)=1
combination([ number[0], number[1], number[2] ] , 3)	i(1)=0, i(2)=1, i(3)=2	num.length 3
combination([ number[0], number[1], number[3] ] , 4)	i(1)=0, i(2)=1, i(3)=3	num.length 3
combination([ number[0], number[1], number[4] ] , 5)	i(1)=0, i(2)=1, i(3)=4	num.length 3
combination([ number[0], number[1], number[num.length-1] ] , num.length)	i(1)=0, i(2)=1, i(3)=num.length-1	num.length 3
combination([ number[0], number[2] ] , 3)	i(1)=0, i(2)=2
combination([ number[0], number[2], number[3] ] , 4)	i(1)=0, i(2)=2, i(3)=3	num.length 3
combination([ number[0], number[2], number[4] ] , 5)	i(1)=0, i(2)=2, i(3)=4	num.length 3
combination([ number[0], number[2], number[5] ] , 6)	i(1)=0, i(2)=2, i(3)=5	num.length 3
combination([ number[0], number[2], number[num.length-1] ] , num.length)	i(1)=0, i(2)=2, i(3)=num.length-1	num.length 3
combination([ number[0], number[3] ] , 4)	i(1)=0, i(2)=3
...
combination([ number[0], number[4] ] , 5)	i(1)=0, i(2)=4
...
combination([ number[0], number[num.length-1] ] , num.length)	i(1)=0, i(2)=num.length-1
combination([ number[1] ] , 2)	i(1)=1
combination([ number[1], number[2] ] , 3)	i(1)=1, i(2)=2
combination([ number[1], number[2], number[3] ] , 4)	i(1)=1, i(2)=2, i(3)=3	num.length 3
combination([ number[1], number[2], number[4] ] , 5)	i(1)=1, i(2)=2, i(3)=4	num.length 3
combination([ number[1], number[2], number[5] ] , 6)	i(1)=1, i(2)=2, i(3)=5	num.length 3
combination([ number[1], number[2], number[num.length-1] ] , num.length)	i(1)=1, i(2)=2, i(3)=num.length-1	num.length 3
combination([ number[2] ] , 3)	i(1)=2
...
combination([ number[3] ] , 4)	i(1)=3
...
combination([ number[num.length-3] ] , num.length-2)	i(1)=num.length-3,
combination([ number[num.length-3], number[num.length-2] ] , num.length-1)	i(1)=num.length-3, i(2)=num.length-2,
combination([ number[num.length-3], number[num.length-2], number[num.length-1] ] , num.length)	i(1)=num.length-3, i(2)=num.length-2, i(3)=num.length-1	num.length 3

 

재귀 과정을 직접 써보았다.
쓰면서 이해는 됐다.
코드를 보고 이해하는 과정을 거치면 앞으로 나도 이런 알고리즘을 떠올릴 수 있지 않을까 🦾✨🌸🐬