함수형 프로그래밍, 클로저, 재귀 함수, 연결 리스트

HongBoogie·2024년 8월 8일

함수형 프로그래밍이란?

프로그래밍 패러다임 중 하나로, 말 그대로 함수를 기반으로 돌아간다. 자스는 기본적으로 객체지향이기 때문에, 완벽히 함수형 프로그래밍을 하긴 힘들다.

함수형 프로그래밍의 원칙으로는

입출력이 순수 함수여야 한다.
side Effect가 없어야 한다.
함수와 데이터를 중점으로 생각한다(객체지향이 객체를 중점으로 보는것과는 다른 방향성)

이 있다.

여기서 순수함수라 함은, 하나 이상의 인자를 받아 받은 인자를 처리해 결과를 리턴해야 한다. 순수 함수는 매개변수 외에 외부의 어떤 값에도 영향을 받지 않는다.
side Effect가 없다는 것은, 개발자가 바꾸려는 변수 외에 부차적인 변화가 없어야 한다는 것이다. 원본 데이터는 불변이어야 한다(자스에선 고차함수를 이용해 구현이 가능하다.). 즉 변수의 사용을 최소화하자는 것이다. 불변성을 지킴으로써 얻을 수 있는 효과는 실행의 흔적을 남기지 않음으로써 예측과 테스트가 용이하고, 변경 이력 관리나 캐싱과 같은 작업에 유리하다.

참조 투명성

함수형 코드의 호출문은 그 반환값으로 대체가 가능하다. 이게 뭔소리냐 하면

const add = (a, b) => a + b;

const add34 = add(3,4);
console.log(add34);

console.log(add34 === add(3,4);

console.log(
	add(add(3,4),5) === add(7, 5);
)

여기서 add(3,4)를 7로 바꿔도 모든 결과가 동일한데, 이는 add 함수가 순수 함수이며, 그 함수의 실행이 외부에 끼치는 변화가 없기 때문에 가능하다.

클로저란?

함수와 그 함수가 선언된 어휘적 환경(Lexical Environment)의 조합을 의미한다.
즉, 함수가 그 당시에 선언 되었을때의 모든 정보(변수, 환경 내의 정보들)을 기억하고, 호출되어 처리가 끝나고 소멸 된 이후에도 그 당시의 모든 정보를 기억하며 접근할 수 있음을 의미한다.
외부/내부 함수와의 관계에서는 외부 함수가 호출되어 실행을 마치고 소멸이 된 이후에도 내부 함수는 외부 함수의 그 당시 선언되었을 때의 환경을 기억하고 있어 이에 접근을 할 수 있음을 의미한다.

일급 객체

일급 객체란 다른 객체들에 일반적으로 적용 가능한 연산을 모두 지원하는 객체를 가리킨다. 보통 함수에 인자로 넘기기, 수정하기, 변수에 대입하기와 같은 연산을 지원할 때 일급 객체라고 한다.

자바스크립트의 함수는 위의 조건을 만족해서 일급 객체가 되고, 일급 함수란 함수를 일급 객체로 취급하는 것을 일컫는다.

재귀 함수란?

항상 헷갈리고 잘 못 사용하던 함수인데 이번 기회에 확실히 정리하기로 했다.

재귀함수는 함수가 자신을 다시 호출하는 구조로 만들어진 함수이다.

재귀의 3가지 중요한 특성

모든 재귀 함수는 3가지의 중요한 특성을 갖습니다.

종료 조건

간단하게, if(나쁜 값이 들어왔다면) { 정지! };과 같이 이해하면 편하다 종료 조건은 재귀의 안전장치이다. 좋지 않은 입력 값이 들어왔을 때, 재귀가 계속하여 동작하는 것을 방지해준다.

기반 조건(Base case, 기저 상태)

간단하게, if(이런 일이 일어난다면) { 성공! }과 같이 이해하시면 된다. 이 조건 역시 재귀 함수를 멈춘다는 점을 감안하면, 기반 조건은 어쩌면 재귀의 종료조건과 비슷하다. 하지만 종료 조건은 모든 나쁜 데이터들을 잡아낸다. 반면에 기반 조건은 재귀 함수의 목적 이다. 기반 조건은 주로 if 문 내부에 있다.

재귀

간단하게, 함수가 자기 자신을 호출하는 것이다.

function f(n) {
    if (n <= 1) {
       return 1 // 종료 조건
    }
    return n + f(n-1) // 재귀함수
}
console.log(f(100)) //5050

이 경우엔, f(n-1)이 n에서 값을 빼며 자기 자신을 호출하여 재귀 함수인 것을 볼 수 있다. f(n) 함수는 종료 조건인 1까지 순회하며 1~ 100까지의 값을 다 더할 것이다.

function strReverse(str) {
    if (str.length == 1) {
        return str //종료 조건
    }
    return str[str.length-1] + strReverse(str.slice(0, str.length-1)); // 순서 더하는 순서 바꾸면 정순
}
console.log(strReverse('jeongwoohong')); //gnohoowgnoej

이름 뒤집기이다. 항상 마지막 글자를 더해주고 함수를 호출해서 길이를 줄인 후 다시 함수를 실행하는 구조이다.

function digitSum(str) {
    if (str.length == 1) {
        return parseInt(str, 10)
    }
    console.log(str.slice(0, str.length-1));
    return parseInt(str[str.length-1], 10) + digitSum(str.slice(0, str.length-1)); // 순서 더하는 순서 바꾸면 정순
}
console.log(digitSum('1231233'));

위랑 비슷하다. 각 문자열의 마지막 문자를 10진수로 변환해 더해주고, 문자열을 잘라주면서 재귀 함수를 돌리는 경우다.

연결 리스트란

연결 리스트는 선형적인 데이터 구조라는 점에서 배열과 유사하다. 하지만 배열과 달리, 연결 리스트의 요소(elements)들은 특정 메모리 주소나 인덱스에 저장되지는 않는다.

오히려 각 요소는 포인터 또는 다음 객체에 대한 링크를 가지는 독립적인 객체에 가깝다.

연결리스트의 각 요소를 노드(node)라고 부르는데, 노드는 일반적으로 데이터, 그리고 다음 노드를 가리키는 링크로 구성된다.

Untitled

연결 리스트의 첫 노드를 헤드(head)라 부른다. 마지막 노드는 null을 가리킨다.
즉, 연결리스트가 비어있는 경우, 헤드는 null을 참조한다.

자스로 비슷하게 구현하면

const list = {
    head: {
        value: 6
        next: {
            value: 10
            next: {
                value: 12
                next: {
                    value: 3
                    next: null
                    }
                }
            }
        }
    }
};