재귀

Dongwoo Joo·2023년 4월 11일
0

codestates bootcamp

목록 보기
28/48

학습 내용

재귀의 이해

재귀 함수

자기 자신을 호출하는 함수

예제

배열의 합을 구하는 arrSum 함수 만들기
입력: [1, 2, 3, 4, 5], 출력: 각 요소들의 합

아래와 같이 배열 요소의 합을 표현할 수 있다.

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

아래와 같이 재귀 함수로 표현할 수 있다.

fuction arrSum(arr) {
    if (arr.length === 0) {
    return 0;
    }
    return arr[0] + arrSum(arr); // 재귀함수 호출
}

재귀의 필요성

  • 문제를 유사한 구조의 작은 문제로 나눌 수 있는 경우
  • 중첩된 반복문이 많거나, 반복문의 중첩 횟수를 예측하기 어려운 경우

재귀의 활용

재귀적 사고

  1. 재귀 함수의 입력값과 출력값 정의하기
    나만의 문제정의 방법
    문제: 입출력 추상화 작성
    타입: 입출력 타입값 작성
    예시: 입출력 예시 작성

어떤 문제를 풀던 간에 마찬가지지만, 문제 정의가 매우 중요하다.
문제 정의를 하지 않고 무작정 문제를 해결하려는 행위는 문제 해결의 의미가 없다.
이는 생각없이 수학문제를 푸는 것과 마찬가지이다.
따라서, 무조건 문제정의를 하고, 입출력 데이터 타입에 유의해야 한다.

  1. 문제의 구성을 파악하고 경우의 수에 따라 구분하기
    3가지로 문제를 구분할 수 있다.
  • 문제를 입력값으로 구분
  • 문제를 크기로 구분
  • 문제의 순서를 명확히 구분
    이렇게 되면 문제가 어떻게 구성되어 있는지 알 수 있다.

다음 작업은 아래와 같다.

  • 전체 문제 -> 작은 문제로 나누기
    위의 예시 코드처럼 arrSum 전체 값을 arrSum 여러 값들로 나눌 수 있다.
  • 문제를 더 이상 나눌 수 없는 경우와 그렇지 않은 경우로 나눈다.
  1. 단순한 문제 해결(Base case)
    문제를 여러 경우로 구분했을 때,
    가장 해결하기 쉬운 문제를 재귀의 기초(base case)라고 한다.
    => 재귀 함수 구현 시, 재귀 호출을 멈추는 조건이 된다.

while문에서 break가 없고 조건이 계속 참일 때, 무한히 반복되는 것처럼,
탈출 조건이 없는 재귀 함수는 무한히 재귀한다.
따라서, 문제를 나눌 수 없을 때까지 작게 나누고, 탈출 조건을 세운다.

  1. 복잡한 문제 해결(recursive case)
    남은 문제(반복되는 문제)를 재귀적으로 추상화한다.

  2. 코드로 구현하기
    재귀 함수의 템플릿

fucntion 재귀 함수 {
    // base case: 문제를 더 이상 나눌 수 없는 경우. break.
    if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 결과
    }
    
    // recursive case: 그렇지 않은 경우(재귀적으로 구현)
    return 더 작은 문제로 새롭게 정의된 문제
    }

아는 것

재귀함수는 base case, recursive case 로 구성된다.
base case는 반복문의 조건과 같이 재귀함수를 멈추는 조건이 된다.
recursive case는 큰 문제를 "같은" 더 작은 문제로 새롭게 정의해서, 잘게 나눈다.

문제(큰 퍼즐)를 반복해서 recursive case를 통해 동일한 퍼즐 피스로 작게 나눈다.
base case에 다다르면, 재귀함수를 멈추고 값을 출력한다.

재귀함수는 매우 유용할 것으로 생각된다.
유사한 데이터 구조에서 데이터를 찾을 때 활용할 수 있을 것으로 생각된다.

느낀 점

어떤 문제를 반복되는 작업으로 풀어야 할 때, 재귀함수를 사용할 수 있다.
내가 느낀 재귀함수는 수학적으로 문제를 풀어야 할 때 정말 유용하게 사용될 것 같다.
피보나치 수열, 무한급수의 합 등등..
그리고 연습문제를 풀면서, 고등학교 때 수열을 풀 때가 많이 생각났다.
재귀함수를 만드는 것은 마치, 수열의 일반항을 구하는 것과 매우 유사했다.

재귀함수와 반복문(Feat.ChatGPT)

재귀 함수와 반복문(for문)은 모두 반복적인 작업을 수행할 수 있는 구문입니다.

재귀 함수는 자신을 다시 호출하여 작업을 수행하는 방식으로 구현되며,
반복문은 일정한 조건이 충족될 때까지 작업을 반복하는 방식으로 구현됩니다.

재귀 함수를 사용할 때는 문제가 잘게 분해되어 작은 단위로 해결될 수 있을 때 적합합니다.
또한, 재귀 함수를 사용하면 코드가 간결해질 수 있습니다.
그러나, 너무 깊은 재귀 호출은 스택 오버플로우(메모리 부족) 문제를 일으킬 수 있으므로,
재귀 함수를 사용할 때는 재귀 호출이 일어나는 횟수를 제한하는 기준을 정하는 것이 좋습니다.

반면, 반복문을 사용할 때는 일반적으로 문제를 단순히 반복하여 해결할 수 있을 때 적합합니다. 또한, 재귀 함수보다는 성능상 이점이 있을 수 있습니다.

최종적으로는 문제의 성격과 상황에 따라서
재귀 함수와 반복문 중 어떤 것을 사용할지 결정해야 합니다.

프론트엔드 프로젝트에서도 재귀 함수를 사용해야 하는 상황이 있습니다.
예를 들어, DOM 트리를 순회하면서 특정 노드를 찾거나, 트리 구조를 다룰 때는
재귀 함수를 사용하는 것이 유용할 수 있습니다.
또한, 어떤 작업을 순차적으로 수행해야 할 때는 재귀 함수를 사용할 수도 있습니다.

그러나, 재귀 함수를 사용할 때는 성능상 이슈가 발생할 수 있으므로, 상황에 따라서 재귀 함수를 사용하는 것이 좋을지 아니면 다른 방법을 사용하는 것이 좋을지 고려해야 합니다.

모르는 것

연습문제를 푸는 동안 내가 잘 모르는 메서드가 있었다.
*모른다는 뜻: 이름은 알지만, 정확히 어떤 기능이 있는지 모르고, 자유자재로 사용하지 못하는 상태

arr.pop(), arr.push(), arr.slice(), arr.concat() 이다.
arr 메서드인 것은 인지하고 있으나, 코드 구현에 있어 자유자재로 사용하지 못하고 계속 MDM을 참고해야 했다. 자주 사용하는 메서드는 완벽히 익혀놓자.

참고 자료

반복문과 재귀 비교를 참고했다.
출처: https://velog.io/@gillog/Algorithm-%EC%9E%AC%EA%B7%80%EC%99%80-%EB%B0%98%EB%B3%B5%EB%AC%B8
이 분의 블로그를 참조해서 중요한 내용만 정리해봤다.
(To. 블로그 주인님께,
너무 좋은 자료라서 꼭 한 번 작성해서 익히고 싶었습니다.
만약 지나치게 참고했다고 지적해주신다면, 지우겠습니다.
좋은 자료 감사합니다.)

구분반복문재귀 함수
실행명령을 반복적으로 실행함수를 호출
체제초기화, 조건, 루프 내 명령문 실행과 제어 변수 업데이트 포함종료 조건만 지정(조건을 추가할 수 있다)
조건break이 없고, 제어 조건이 참이라면 무한 루프 발생조건에 수렴하지 않을 경우 무한 재귀 호출
무한 반복무한 루프는 CPU 사이클을 반복적으로 사용무한 재귀는 stack overflow 발생
스택 메모리스택 메모리를 사용하지 않음함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합, 함수 호출 위치를 저장하는데 사용
속도실행이 빠르다실행이 느리다
가독성코드 길이가 길어지고 변수가 많아져서 가독성이 떨어진다코드 길이와 변수가 적어 가독성이 높아진다.

재귀 함수는 stack이라는 메모리 공간을 사용한다.
반복적으로 자기 자신(재귀 함수)을 부르면서 stack에 계속해서 재귀 함수가 쌓여가기 때문에 성능이 좋지 않다.

재귀함수는 stack이라는 메모리 공간을 계속해서 이용하기 때문에,
무한 재귀가 발생할 경우 메모리의 제한이 있는 한,
stack overflow가 뜨면서 프로그램이 비정상 종료된다.

반복문의 경우엔 stack 메모리를 재귀 함수처럼 사용하지 않아,
프로그램이 종료되지 않고 무한 실행된다.

재귀함수가 반복문보다 느리지만,
그럼에도 불구하고 재귀함수를 사용하는 이유가 있다.

  1. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우
    재귀함수로 간단히 표현되는 경우에, 유용하다.

  2. 변수 사용을 줄여줄 수 있다.
    변수 사용이 줄어든다는 것은, 결과적으로 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다.
    mutable state를 줄일 수 있다. 또, side effect가 없다.

직관적이지 않은 재귀 호출이 이해하기 어려울 수도 있다.
하지만 프로그램이 복잡해지면, 변수가 변하는 상황들을 가능한 피하는 것이,
오류 없는 프로그램을 짜는 데에 중요한 사항이 된다.

  1. 가독성이 향상된다.
    반복문에 비해, 재귀 함수는 코드 가독성 측면에서 코드량이 줄어든다.
    또한, 사용하는 변수가 줄어들어 가독성이 향상된다.

결론
성능만 본다면 재귀함수는 사용하지 않는게 맞다.
반복문에 비해 메모리나 속도 등 성능적 측면에서 많이 뒤쳐지기 때문이다.

하지만 현재는 하드웨어 성능이 매우 낮아,
소프트웨어 속도를 극한까지 끌어올려야 하는 시대가 아니다.
협업을 생각한다면 가독성도 고려해 프로그래밍을 해야 한다.

따라서, 프로그램의 목적을 고려해서 재귀 함수를 사용하는 것이 올바르다.
복잡한 반복문을 재귀 함수로 간단하게 구현할 수 있기 때문이다.

자 오늘 재귀 함수로 피보나치 수열을 구현한 기념으로,
피보나치 관련 사진을 찾았다.
은하계는 피보나치 수열로 모인다고 하는데, 정말 아름답지 않은가?
수학과 프로그래밍의 신비함.. 계속 탐구하고 싶다.

profile
pursue nature

0개의 댓글