[알고리즘] 재귀함수와 반복문에 대해서

Q1. 재귀함수를 쓰는 이유

- 01. 재귀와 반복문을 비교해보기

[재귀 함수]

자기 자신을 호출하는 함수 ex) 피노나치 수열, 하노이의 탑 알고리즘, 팩토리얼 등등 .. 

• 기본 : 함수 자체를 호출 한다
• 체재 : 기본적으로 종료 조건만 지정 한다 (조건이 추가 될 수도 있음)
• 종료 : 조건부 문은 함수 호출 본문에 포함되어 재귀 호출을 실행하지 않고 함수를 강제로 반환한다
• 조건 : 기본적으로 조건에 수렴하지 않으면 무한 재귀가 발생한다
• 무한반복 : 무한 재귀는 스택 오버플로우를 일으킴
• 스택 메모리 : 스택 메모리는 함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합을 저장하는데 사용
• 속도 : 느린 실행
• 가독성 : 코드 길이와 변수가 적어 가독성이 높아짐

(특징)

1. 코드의 가독성이 좋다

2. 스택 메모리를 사용한다. 

 

[반복문]

for 문 

• 기본 : 일련의 명령을 반복적으로 실행할 수 있다
• 체재 : 반복에는 초기화, 조건, 루프 내의 명령문 실행 및 제어 변수 업데이트가 포함
• 종료 : 특정 조건에 도달 할 때까지 반복적으로 실행
• 조건 : 반복문의 제어 조건이 참이라면 무한 반복이 발생
• 무한반복 : 무한 루프는 CPU 사이클을 반복적으로 사용
• 스택 메모리 : 스택 메모리를 사용하지 않음
• 속도 : 빠른 실행
• 가독성 : 코드 길이를 더 길게 만들고 변수가 많아 가독성이 떨어짐

 

	재귀함수	반복문
정의	함수를 다시 호출하여 반복작업 실행	명령을 반복적으로 실행
스택 메모리	함수 호출 시 함수의 매개변수, 지역변수, 리턴값, 함수 종료 후 돌아가는 위치가 스택메모리에 저장	스택 메모리를 사용하지 않음
무한 반복 시	무한 재귀는 스택 오버플로우 발생	무한 루프는 CPU 사이클을 반복적으로 사용
속도	느린 실행	빠른 실행

---

- 02. 재귀와 반복문의 차이 

1. 메모리 

재귀함수는 함수를 반복적으로 호출하기 때문에 스택 메모리를 사용한다. ( 스택 오버플로우 발생 )

※ 스택오버플로우(stack overflow)란?
재귀함수 사용 시, 함수를 반복적으로 호출하므로, 스택메모리에 콜 스택이 쌓이게 된다. 이때 함수를 호출하는 횟수가 많아진다면 스택메모리를 초과하여 stack overflow가 발생하는 것이다. (일반적인 반복문 사용 시, 지역 변수들이 호출될 때 한번만 할당되기 때문에 이러한 일이 발생하지 않는다.)

반복문은 메모리 힙을 사용

2. 코드 길이 

재귀함수를 사용하면 반복문에 비해 코드 길이를 줄일 수 있다. 

---

- 03. 재귀 함수를 사용하는 두가지 이유

• 알고리즘 자체가 재귀적인 표현이 자연스러운 경우 ( + 가독성 )  
  • f(n) = f(n - 1) + f(n - 2)
• 변수 사용 을 줄일 수 있다.
  변수 사용을 줄여준다는 것은 변수가 잡는 메모리에 대한 이야기가 아니라, mutable state(변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기이다. mutable state 를 최대한 피하는 것은 변수의 수를 줄이는 것과 변수가 가질 수 잇는 값의 종류 또는 범위를 정확히 제한하는 것이라고 생각하면 된다.  점화식을 보면, 결국 f(n)을 구하기 위해선 f(n - 1), f(n - 2)라는 자기자신의 함수를 인자만 바꾸고 다시 호출해야 한다. 이런 경우엔 반복문도 가능하지만, 재귀함수를 이용해서 간단히 구할 수 있다. 대부분 많은 사람들이 이 이유 때문에 재귀함수를 자주 사용 한다.

 

반복문의 예

let sum = 0;
for(let i = 0; i <= 100; i++) {
  sum += i;
}

 

재귀 함수

function sum(x) {
  if(x === 100) return x;
  else return x + sum(x + 1);
}

sum(0)

=> 변수 사용이 줄어든다 

 

 

반복문

function fibonacci(n) {
  let pre = 0;
  let cur = 1;
  let last = 0;
  for(let i = 1; i < n; i++){
    last = pre + cur;
    pre = cur;
    cur = last;
  }
  return last;
}

 

재귀 함수

function fibonacci(num) {
  if(num < 2) return num;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

---

Q2. 왜 퀵소트를 가장 많이 쓰는 걸까? (