자료구조와 알고리즘 2장 재귀

TIL 날짜

2023.11.28 ~ 2023.11.29

 

Contents

1. 의미 및 요소
2. 재귀 함수
3. 사용하는 이유
4. 예시
5. 재귀 함수 vs 일반 함수
6. 헬퍼 메소드
7. 순수 재귀

의미 및 요소

의미: 원래의 자리로 되돌아오는 것 및 종료점에 도달할때까지 반복적으로 수행하는것

요소

• 분할 정복
  큰 문제를 작아진 부문제들로 쪼개서 문제 해결 
• 베이스 케이스
  종료 지점을 지정해줘야 한다. 지정해주지 않으면 무한루프
• 스택 활용
  스택에 새로운 프레임을 추가, 함수의 호출이 계속되는 동안 중간결과를 저장하고 복구하는 데 사용

재귀 함수

의미: 함수 내부에서 자기 자신을 호출하는 함수

규칙: 기반조건이 있어야 한다, 재귀가 반복될 때마다 다른 인풋값이어야 한다.

장점

• 가독성: 재귀적인 호출을 통해 코드를 간결하게 작성할 수 있습니다.
• 직관적: 코드의 반복문 대신 재귀 함수를 사용하여 직관적으로 나타낼 수 있다.

단점

• 스택의 깊이: 함수를 호출할때마다 프레임이 생겨 스택의 범위를 초과할수 있다.
• 속도: 함수의 호출이 반복적으로 발생하기에 속도가 느려진다.

재귀를 사용하는 이유

• 재귀는 자바스크립트(Json.parse)같은 많은  프로그래밍 언어에서 사용한다.
• 가독성이 높다
• 문제를 잘게 부숴서 해결하는데 큰 도움을 준다.

재귀의 예시

function countDown(num){
	if(num <=0){
	console.log("All Done")
	return
}	console.log(num);
	num--
	countDown(num)
}

 

재귀 함수 vs 일반 함수

차이점	재귀 함수	일반 함수
성능	반복문에 비해 성능이 떨어짐	반복문을 사용 시 성능 우수
호출 방식	함수 내부 및 외부	함수 외부
종료 조건	필요 O	필요 X
프레임 추가	O	X
가독성 및 유지보수	가독성 ↑ 유지보수 ↓	가독성 ↑ 유지보수 ↑

 

헬퍼 메소드

의미: 재귀적이지 않은 외부 함수가 재귀적인 내부 함수을 호출하는 패턴

예시

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

  function helper(helperInput) {
    // if절은 종료조건
    if (helperInput.length === 0) {
      return;
    }

    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0]);
    }
    helper(helperInput.slice(1));
  }
  helper(arr);
  return result;
}
console.log(collectOddValues([1, 2, 3, 4, 5]));
// 출력값: [1,2,3]

 

순수 재귀

의미: 재귀 함수가 자신을 호출할 때 전역 변수를 사용하지 않고, 함수의 입력 값만 의존하여 동작하는 재귀적인 패턴

특징

• 부수효과 없음: 함수가 호출될 때 전역 변수를 변경하거나 함수 외부의 상태에 영향을 주지 않는다.
• 전역변수 사용없음: 매개변수만을 사용하여 동작한다.
• 불변성 유지: 함수 내부에서 매개변수로 받은 값을 변경하지 않고 새로운 값을 반환

예시

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}