JS 자료구조 & 알고리즘 - 재귀

재귀 함수란

자기 자신을 호출하는 함수를 말한다.

• 재귀 함수의 필수요건
  1. 종료 조건 (라인을 끝내는 지점)
  2. 다른 입력값

JS 에서 함수를 호출할때 발생하는 일

• JS는 call Stack이라는 구조 안에서 함수가 실행 된다.

call Stack은 이름 그대로 stack 자료구조를 사용하고 있다.

call Stack에는 우리가 호출한 함수가 늘 제일 위에 위치하게 된다.

callStack으로 호출된 함수는, return 키워드를 확인하거나, 더이상 실행할 코드가 없으면

컴파일러 가 callStack의 최상단에 있는 지금 실행중인 함수를 제거한다.

나중에 들어온함수가 제일 먼저 사라지게 되는 구조!

LIFO 라고 한다.

간단한 재귀함수

function countDown(num) {
	if(num <= 0) {
		console.log("all done");
		// 함수를 종료하는 종료 조건!
		return;
	}
	console.log(num);
	num--; //다른인수를 입력하기 위한 인수 변경
	countDown(num);
}

function factorial(num) {
    if (num === 1) return 1;
    return num + factorial(num -1);
}

• 내부의 재귀 return 문이 factorial(num -1)을 계속호출하게 되는데, 이때, return문은 재귀호출한 함수가 결과를 반환할 때 까지 대기 한다.
• return 문을 쓰지 않으면?
  • 결과적으로 재귀로 호출하게 되는 함수의 반환값을 사용하지 못하게 된다.
  • return 문은 함수 탈출의 역할 을 하기에, return을 통해 다중 재귀를통해 호출된 함수의 종료를 알려야 한다.

팩토리얼 함수 구현하기

• 일반 loop 이용

function factorial_loop(num) {
	let total = 1;
	for (let i = num; i > 0; i--) {
		total *= i
	}
	return total;
}

• 재귀 함수이용

function factoral_reculsion(num) {
	if(num === 1) return 1;
	return num * factoral_reculsion(num -1);
}

재귀의 잠재적인 위험

• 종료 조건이 없는 경우
  • 종료 조건이 없다면, 해당 재귀함수는 영원히 자기 자신을 호출하여 Call Stack에 함수를 쌓으므로 무한 Loop적 오류를 초래한다.
• 필요한 곳에 return (반환문) 을 사용하지 않는 경우
  • 의도하지않은 코드 흐름이 발생할 수 있다.

Helper 메소드 재귀

함수 하나를 하나의 블록 개념으로 스페이스를 만들어 그안에 재귀함수를 작성하여

사용 변수를 전역으로 선언하지 않고 함수 내의 전역 변수로만 활용

function collectOddValues(arr) {
    let result = [];

    function helper (helperInput) {
        if (helperInput.length === 0) {
            return;
        }

        if (helperInput[0] % 2 !== 0) {
            result.push(helperInput[0]);
        }

        helper(helperInput.slice(1))
    }

    // 재귀 함수 본격적으로 호출
    helper(arr)

    return result;
}

• 위 collectOddValues의 실제 논리는 내부 함수 helper에 작성이 되어 있다.
• helper함수에서 감싸고 있는 함수, 즉 외부 함수인 collectOddValues의 내부 변수 result에 결과 값을 계속 추가하는 것으로 보아 collectOddValues함수는 실질적으로 코드 스페이스의 역할을 한다.
• 이렇게 작성하면, 전역적으로 깔끔한 코드스타일을 유지 할 수 있고, wrapper함수내부의 환경에 신경쓰기만 하면 되기 때문에, 일관된 코드 스타일 유지도 가능해진다.

순수 재귀 (Pure Reculsion)

위의 collectOddValues 함수를 순수 재귀 의 방식으로 작성해본다.

순수 재귀의 경우 필요한 모든 코드가 함수 자체에 포함되며 재귀적이다.

function collectOddValues(arr) {
    let newArr = [];
    if (arr.length === 0) {
        return newArr
    }

    if(arr[0] % 2 !== 0) {
        newArr.push(arr[0])
    }

    newArr = newArr.concat(collectOddValues(arr.slice(1)))
    return newArr
}

내부의 newArr은 함수의 실행마다 초기화 되는 것이 맞지만, 마지막 newArr할당 구문을 통해서 계속해서 재귀 호출한 함수의 반환 값을 concat 한 후 return 함으로 최종적으로는 홀수만 골라낸 배열이 완성 된다.

순수재귀와 helper 메소드 재귀 방식에 대해서는 어떤 방식 늘 옳다고 단언할 수 없다고 생각한다.

다만 각 방식에 대한 완벽한 이해를 필두로 최적의 방법을 채택하여 작성하는 것이 옳다고 생각한다.

너무 당연한 소리인가??

연습문제

숫자를 인수로 받아 피보나치 수열의 n 번째 숫자를 반환하는 함수 작성

내가 작성한 답

function fib(num){
  // add whatever parameters you deem necessary - good luck! 
  let arr = []
  let temp = 1;
    function helper(helperInput){
        console.log(arr)
        if(helperInput === 0) return;
        
     
        if(arr.length === 0) {
            arr.push(1);
            
        } else if(arr.length === 1) {
            arr.push(arr[0]);
            
        }else if(arr.length > 1) {
            arr.push(arr[arr.length - 1] + arr[arr.length - 2])
            
        }
        
        helper(helperInput - 1)
    }
    helper(num)
    return arr[num-1]

}

강의의 답

function fib(n){
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}