재귀(Recursion)
자기자신을 호출하는 함수를 말한다. 특정 분기(기저조건)까지 자기 자신을 계속 호출하므로 반복문을 대신하여 구현할 때 사용한다.
재귀함수의 장점과 단점
장점
반복문에 비해 재귀함수가 갖는 장점은 무엇일까? 무엇보다 코드가 더 간결해진다는 점이 있다. 특히 반복문에선 tmp 임시변수를 만들어서 현재 상태를 저장해야하는 부분이 있었다면, 재귀함수를 사용하게 되면 변경된 상태를 전달 함으로써 재귀적으로 호출하게 되므로 변수의 수를 줄일 수 있다.
단점
중첩함수에서 지속적으로 함수를 호출하면서 제어 흐름의 현재 위치, 변수의 현재 값 등을 실행 컨텍스트 스택에 저장하므로 선언한 변수의 값만 사용하는 반복문에 비해 메모리를 더 많이 사용하게 되며, 이는 속도의 저하로 이어진다.
뿐만 아니라 치명적인 단점으론 기저조건을 설정해주지 않으면 무한히 자기자신을 호출하게 되고, 컴퓨터 메모리의 한계로 인한 스택 오버플로우(stack overflow)로 이어지게 된다.
재귀적 자료구조 - 연결 리스트
장점
배열을 사용할 때 단점으로는 arr.push(prop), arr.pop()메서드에 비해 arr.unshift(), arr.shift()메서드는 배열의 앞쪽에 요소를 "삽입"하거나 "삭제"하므로 연산 수행이 오래걸려 느리다. 이럴 때 연결 리스트를 사용하면 좋다. 연결 리스트는 value, next프로퍼티를 갖는 객체로, 특히 next는 다음 연결 리스트 요소를 참조하는 프로퍼티이다. (마지막 요소일 땐 null이다.)
그런데 사람들은 연결 리스트를 많이 사용하지 않는다. 왜일까? 인덱스를 통해 해당값에 바로 접근할 수 있는 배열과 달리 연결 리스트는 N번째 항목에 접근하기 위해선 N번 next로 이동해야한다.
실행 컨텍스트와 스택
실행 컨텍스트란 함수 실행의 세부 내용을 담은 내부 데이터 구조라고 할 수 있다. 여기엔 변수의 현재 값, 제어흐름의 현재위치 등의 정보가 담겨있다.
특히 함수 내부에 중첩호출이 실행될 때, 현재 함수의 실행이 멈추고 함수의 실행 컨텍스트가 실행 컨텍스트 스택에 저장된다. 그리고 중첩함수가 리턴될 때 차례로 실행 컨텍스트 스택에 쌓인 실행 컨텍스트들이 위에서 부터 리턴된다. 이를 재귀함수와 연관지어 생각해보면 아래 문제(단일 연결 리스트 역순으로 출력하기)를 해결할 수 있다.
처음에는 해당 문제의 알고리즘이 이해가 가질 않았는데 정리해보면 아래와 같다.
- 함수 recursion(list)를 호출하고, 실행 컨텍스트에 세부 내용이 저장됩니다.
- 조건문이 true이므로 recursion(list.next)를 호출하게 되면서 현재 함수의 실행이 멈추고 실행 컨텍스트 스택에 세부 내용이 저장됩니다. (이것을 반복하며 실행 컨텍스트 스택에 쌓이게 됩니다.)
- list.next가 null이 되면서, 조건문이 false가 되므로 멈췄던 현재 함수의 실행이 계속되면서 console.log(list.value)가 실행됩니다.
참고: "", null, undefined, 0, NaN 은 false가 반환됨 - 실행 컨텍스트 스택에 쌓여있던 실행 컨텍스트가 위에서 부터 차례로 반환됩니다.
- 그러므로 해당 재귀함수의 재귀의 깊이는 실행 컨텍스트 수의 최댓값과 같습니다.
☑️ 참고
