반복문

특정 조건을 만족하지 못할 때까지(while, repeat-while) 또는 더 이상 확인할 요소가 없을 때까지(for-in)
블락 내부를 반복적으로 수행하고 반복문을 빠져 나온다.

Memoization. 피보나치 수열을 통해 반복문, 재귀함수와 비교하기

ex. 피보나치 수열

: 재귀함수의 시간복잡도가 더 나쁘다.

(이유: 재귀함수는 다른 함수 호출 할 때마다 2 갈래로 나뉨O(2^N).
반면, 반복문은 기존값에 누적해서 반복적으로 더하기 때문에 O(N))

장점

흐름 파악이 상대적으로 쉽다

단점

반복되는 연산을 매번 새로 수행해야한다.

반복문 실행을 위한 조건문 작성에 신경써야한다.

재귀함수

함수 내부에서 동일한 함수를 호출해서 동일한 코드를 반복적으로 수행하고
”return에” 또는 “void를 반환하는 경우에는 함수 끝에” 도달하게 되면
하나씩 호출한 함수로 돌아가면서
최초로 호출한 함수에 도달하면 반복 구문이 종료하게 된다.

[알고리즘] 반복과 재귀, 팩토리얼 재귀 함수, 하노이탑

ex. 하노이 탑
(이유:
마지막 하나 남았을 때의 상황이 N-1일 때도 동일
→ 마지막 순간을 생각하면 이전은 동일해서 구현 쉬움
→코드 구성이 단순해진다)

장점

간단히 함수 호출로 반복적으로 수행가능하다.

동일한 연산을 반복해서 수행할 필요 없이 이전에 계산한 결과를 활용할 수 있다.

단점

흐름 파악이 어렵다. → 복잡도 계산이 어렵다.

탈출 구문 작성에 신경써야한다.

오버헤드가 크다. → 메모리 사용량 많음(돌아갈 포인트 기억해야함)