[알고리즘]재귀

💡학습 전 보기 - 재귀 함수 등 정리

 

목표

• 재귀의 정의와 재귀 사용 방법 정의
• 재귀 함수의 두 가지 필수 구성 요소 이해
• 호출 스택을 시각화하여 재귀 함수를 더 잘 디버그하고 이해하기
• 헬퍼 메소드 재귀(helper method recursion)와 순수 재귀(pure recursion)

재귀를 한번에 이해하는 것은 쉽지 않다. 지속적인 반복으로 자신의 것으로 만들자.

 

재귀(recursion)란?

자기 자신을 호출하는 프로세스 즉, 자기 자신을 호출하는 함수를 의미한다.

 

 

재귀를 알아야하는 이유는 무엇일까?

재귀는 어디서든 사용된다. 

• JSON.parse / JSON.stringify
• document.getElementById and DOM traversal algorithms
• Object traversal
• 복잡한 데이터 구조
• 반복(iteration)을 사용하는 것보다 깔끔한 대안이 될 수 있다.

자신만의 데이터 구조를 만들고, 트리나 그래프를 생성하고, 데이터 구조/트리/그래프를 순회하고, 그 안에 있는 요소를 검색하고자 하는 경우 해결책에 재귀가 포함될 때가 많다. 

 

재귀 함수 내에는 재귀 호출을 멈출 수 있는 탈출 조건(base case)을 반드시 만들어야 한다.

 

재귀 함수는 반복문 없이 구현할 수 있다는 장점이 있지만 무한 루프에 빠질 위험이 있기에 재귀 함수를 사용하는 편이 더 직관적으로 이해하기 쉬울 때 한정적으로 사용하는 것이 바람직하다.

 

재귀를 쓰는 이유

1. 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때. (가독성 이야기)
2. 변수 사용을 줄여 준다.

변수 사용을 줄여준다는건 변수가 잡는 메모리에 대한 이야기가 아니라,
mutable state (변경 가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기다.

 

재귀 함수를 쓰지 않는 이유는 메모리를 많이 차지하며 성능이 반복문에 비해 느리다.

함수를 호출 시 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장된다.

재귀 함수를 쓰게 되면, 함수를 반복적으로 호출하므로, 스택 메모리가 커지고, 호출하는 횟수가 많아지면 스택 오버플로우가 발생할 수 있다.

또한 스택 프레임을 구성하고 해제하는 과정에서 반복문보다 오버 헤드가 들어 성능도 느려진다.

이 부분에 관해선 나중에 다시 언급될 예정이다.

 

거의 모든 프로그래밍 언어에는 함수가 호출될 때 일어나는 일을 관리하는 내장 데이터 구조가 있다.

이것을 콜 스택(call stack)이라 한다.

함수를 호출하면, 호출 스택(call stack)의 꼭대기에 쌓인다.  새로 추가하는 함수가 제일 꼭대기에 위치하게 된다. 

자바스크립트가 return 키워드를 확인하거나, 함수 안에 더 이상 실행할 코드가 없으면 컴파일러(compiler)가 스택의 제일 위에 있는 항목을 제거할 것이다. 

function takeShower() {
    return '씻자'
}

function eatBreakfast() {
    let meal = cookFood()
    return `${meal} 먹자`
}

function cookFood() {
    let items = ['카레', '계란', '김치 찌게']
    return items[Math.floor(Math.random()*items.length)];
}
function wakeUp() {
    takeShower()
    eatBreakfast()
    console.log('일하러 가자')
}

wakeUp()

호출 스택

위는 호출 스택의 개념을 알기위해 사용한 예시이다.

근본적인 개념은 함수가 호출되면 스택의 꼭대기에 추가되고, 꼭대기에서 한 번에 하나씩 제거된다.

호출 스택은 코드 실행 중에 함수 호출을 관리하는 데 사용되는 데이터 구조로, 메모리 상의 스택 프레임(함수의 실행 컨텍스트)을 사용하여 호출된 함수의 정보를 추적한다. 이 스택은 동적으로 변하는 런타임 데이터 구조이다. 

function countDown(num) {
  if(num <= 0) {
    console.log('All done!');
    return;
  }
  console.log(num);
  num--;
  counDown(num);
}

위 코드는 간단한 재귀 함수의 예시이다. num이 0 혹은 그 이하일 때 탈출하도록 하였다.

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

sumRange(3)
     return 3 + sumRange(2)
                reutnr 2 + sumRange(1)
                           return 1

재귀를 이야기할 때 factorial을 주로 예시로 든다. factorial 구현 예시는 이 글 맨 위 링크에 들어가면 볼 수 있다.

 

재귀의 잠재적 위험

• No base case: 탈출(종료) 조건이 없을 때
• 값을 반환하는 걸 잊었을 때
• 잘못된 값을 반환하는 것 

헬퍼 메소드 재귀(Helper Method Recursion)

다른 자료구조나 데이터를 선언하여, 그곳에 알고리즘 조건에 해당하는 결괏값을 담아 return 하는 방식

function collectOddsValues(arr) {
    let result = []

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

        if(helperInput[0] % 2 !== 0) {
            result.push(helperInput[0])
        }
        helper(helperInput.slice(1)) // 0을 제외한 1부터 n까지 전부를 인자로 하고 helper 재호출
    }
    helper(arr)
    return result;
}

위와 같이 작업하는 이유는 result를 재귀 함수 안에 정의하면 함수가 호출될때 마다 빈 배열로 리셋되기 때문이다. 헬퍼 메소드 재귀를 사용하면 그런 문제를 해결할 수 있게 된다. result변수를 전역으로 선언해서 사용할 수 있겠지만 전역에서 변수를 선언하는 것은 피해야 한다. 

 

정리하자면, 헬퍼 메소드 재귀는 재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴이다.

 

순수 재귀(Pure Recursion)

헬퍼 메소드 재귀가 한 가지 전략일 뿐 유일한 방법은 아니다. 순수 재귀를 사용해서 같은 작업을 수행할 수 있다.

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

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;
}

collectOddValues([1,2,3,4,5])

[1].concat(collectOddValues([2,3,4,5]))
                  [].concat(collectOddValues([3,4,5]))
                            [3].concat(collectOddValues([4,5]))
                                       [].concat(collectOddValues([5]))
                                                 [5].concat(collectOddValues([]))
                                                            []

헬퍼 메소드와 달리 함수가 호출될 때마다 newArr를 정의한다. 하지만 상관없다. 계산이 완료됐을 때 모든 배열을 하나의 배열로 합쳐 반환하기 때문이다. 빈 배열과 5가 합쳐지면서 5가 반환되고 또 빈 배열과 5가 합쳐지면서 5가 반환되고 3과 5가 합쳐서 3,5가 반환되고 3,5와 빈 배열이 합쳐서 3,5가 반환되고 최종적으로 1,3,5가 합쳐서 newArr에 반환되면서 newArr가 리턴된다. 

 

순수 재귀를 사용하는 팁

• array의 경우 slice, spread연산자, concat등과 같은 배열 메소드를 사용하여 배열을 변경하지 않도록 한다.
• 문자열은 변경할 수 없으므로 slice, substr, substring을 사용하여 복사본을 만들어 준다.
• 객체의 경우 Object.assign 또는 spread 연산자를 사용하여 복사본을 만들어 준다. 

 

 

 

#2022-09-28 내용 업데이트

추후 지속적인 업데이트 예정