[Udemy] 재귀 함수란 무엇인가?

재귀 함수란?

Recursion, 자기 자신을 호출하는 함수

 

접근 방법

한 가지 문제를 가지고 end point(종료점)에 도달할 때 까지 더 작은 부분이나 변경되는 부분에서 반복적으로 수행한다.

 

사용 하는 이유

- 모든 곳에 사용된다.

- JSON.stringify, JSON.parse, DOM 등...

- 반복문으로 해결 가능한 문제를 재귀적으로도 접근할 수 있다.

 

기본 요소

1. 종료 조건

 

종료 조건이 무조건 있어야 한다. 그렇지 않으면 무한 루프에 빠지게 된다.

 

2. 다른 입력값

 

재귀 함수가 return 값을 제대로 정의하지 않거나 처음 호출할 때 사용한 매개변수와 다른 값을 사용하지 않는다면 잘못된 값을 반환하게 된다.

 

재귀 함수 종류

1. helper 메소드

 

결과를 저장하여 사용해야할 때 사용되는 패턴

재귀적이지 않은 외부함수가 재귀함수를 호출하는 패턴

function collectOddValues(arr) {
    const 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;
}

 

 

2. 순수 재귀 함수

 

외부 데이터를 참조하지 않고 재귀 함수 내부의 데이터만 참조하는 재귀함수

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
}

 

배열을 복사하는 slice, concat, spread 연산자 등의 메서드를 사용하여 재귀함수 결과값을 합쳐준다.

문자열은 불변(immutable)하므로 slice, 배열화 하여 진행한다.

객체는 Object.assign, spread 연산자를 사용하여 복사할 수 있다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의