-
(자연수) 리스트의 합을 구하는 알고리즘
1. 변수 sum을 0으로 초기화
2. 순차적으로 리스트의 구성요소에 접근하면서 sum을 더함
function arrSum(arr) { let sum = 0; for (let i = 0; i < arr.length; i++) { sum += arr[i]; } return sum; }
이 문제를 다른 각도에서 생각해보자.
자연수의 리스트 [10, 6, 4, 3]의 합을 구한다고 가정1. [10, 6, 4, 3]의 합을 구하는 건 신경 쓰지 않고, 대신에 [6, 4, 3]의 합을 구하는 방법을 생각
2. [10, 6, 4, 3]보다는 [6, 4, 3]가 더 작으니 왠지 더 쉽게 풀릴 것 같다. [6, 4, 3]의 합을 구하는 방법을 알아낸다면, 이 값에 10을 더하면 원래의 목적인[10, 6, 4, 3]의 합을 구할 수 있음
3. [6, 4, 3]의 합을 구하는 것도 조금 버겁게 느껴져서, 대신에 [4, 2]의 합을 구하는 방법을 생각
4. [4, 2]의 합을 구하는 것도 조금 버겁게 느껴져서, 대신에 [2]의 합을 구하는 방법을 생각
5. [2]의 합을 구하는 건 매우 간단 => 2
이 과정을 간단한 코드로 표현
arrSum([10, 6, 4, 3]) = 10 + arrSum([6, 4, 3]); arrSum([6, 4, 3]) = 6 + arrSum([4, 3]); arrSum([4, 3]) = 4 + arrSum([2]); arrSum([3]) = 3 + arrSum([]); arrSum([]) = 0;
이처럼 어떠한 문제를 해결할 때,
구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 한다.
재귀 함수 사용 코드
function arrSum(arr) { let head = arr[0]; let tail = arr.slice(1); if (arr.length === 0) { return 0; } return head + arrSum(tail); }
스택 오버플로우(stack overflow)
함수는 메모리에 각자의 공간을 할당하고 이를 호출 스택에 할당한다.
함수가 계속해서 호출되다보면 메모리는 한정된 공간이므로 언젠간 가득 차서 함수를 호출할 수 없는 상황이 된다.
이때 발생하는 에러를 스택 오버플로우라고 한다.
재귀 함수와 메모리 사용량 간의 관계(javascript recursion memory leak)
- 재귀 함수는 반복문에 비해 메모리를 많이 차지
- 재귀 함수를 사용하면 함수를 반복적으로 호출하므로 스택 메모리가 커지고, 스택오버플로우가 발생할 수 있음
- 반복문 기반 알고리즘을 통해 알고리즘을 사용하여 메모리 절약
꼬리 재귀(tail call recursion)
재귀 함수의 위와 같은 단점을 보완하고자 꼬리 재귀라는 기법을 사용할 수 있다.
public int recursive(int n) { if (n == 1) { return 1; } return n + recursive(n - 1); } public int tailRecursive(int n, int acc) { if (n == 1) { return acc; } return tailRecursive(n - 1, n + acc); }
두 함수의 큰 차이는 다음 호출을 위한 파라미터의 연산이 어디서 일어나는가의 차이이다.
즉, 다시 말해 return 문에 연산이 있느냐 없느냐 차이
꼬리 재귀는 연산이 return 문 이전에 이루어지고 다음 함수 호출 시 파라미터를 통해 필요한 연산의 결과를 전달하고
함수가 호출되는 시점에 컴파일러는 꼬리 재귀를 최적화하게 되는데, 이 과정에서 꼬리 재귀는 반복문으로 변경된다.
기존의 재귀 형태를 최적화 가능한 형태로 변경하면서 컴파일 시 반복문으로 해석될 수 있도록 만들면 기존에
문제였던 메모리와 성능에 대한 문제를 해결할 수 있다.
'Note' 카테고리의 다른 글
this, 화살표 (0) 2020.10.27 node.js와 관련 도구 (0) 2020.10.27 고차함수, 콜백함수 (0) 2020.10.27 HTML (0) 2020.10.27 Scope, Closure (0) 2020.10.27