함수를 재귀적으로 호출하기

반복과 재귀는 복잡한 작업을 하나씩 작게 나누어 처리하고 그 결과를 조합한다는 면에서는 동일하다.

◾ 반복

필요한 처리를 계속 반복하면서 유지하는 것을 강조. 파일 스트림을 끝까지 읽을 때처럼 한계치까지 특정 처리를 실행할 때 주로 사용된다.

◾ 재귀

작업을 해결할 수 있을 때까지 작은 조각으로 나누는 것을 강조. 팩토리얼 등을 계산할 때 주로 사용된다.

반복으로 함수 호출

int factorial(int n)
{
    int result = 1;
    for (int i = 1; i <= n; ++i) result *= i;
    
    return result;
}

for (int i = 1; i < 10; ++i)
    std::cout << i << "! = " << factorial(i) << '\n';

재귀로 함수 호출

int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

for (int i = 1; i < 10; ++i)
    std::cout << i << "! = " << factorial(i) << '\n';

재귀 호출이 많아지면 콜스택이 쌓여서 결국 스택 영역이 부족해지는 문제가 발생하게 되는데, 이 문제는 뒤에서 나올 꼬리 재귀에서 다룬다.

물론 위의 코드같은 경우는 콜스택이 쌓이기 전에 오버플로우로 인해 프로그램이 미정의 동작을 하게 될 수 있다.

불변 함수 반복 호출

재귀 함수는 상태를 변경할 필요가 없기 때문에 함수형 프로그래밍과 매우 잘 어울린다.

int fibonacci(int n)
{
    if (n == 0) return 0;
    
    int previous = 0;
    int current = 1;
    
    for (int i = 1; i < n; ++i) { // 값의 변경이 일어났기 때문에 순수 함수가 아니다
        int next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

반복문을 사용하는 함수의 경우 값이 변하기 때문에 불변 객체가 아니다.

int fibonacci(int n)
{
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

재귀를 사용하면 코드가 간결해질 뿐만 아니라 자연스럽게 불변 객체가 된다.

마찬가지로 아직까지는 콜스택이 쌓이는 문제가 있다.

불변 객체의 주요 특징

함수형 프로그래밍의 특징인 불변성을 따르려면 지역 변수를 변경하면 안되고 함수 내에서 전역 변수에 접근하면 안된다.

생성 이후 상태를 바꿀 수 없는 객체를 의미한다.

지역 변수 수정

int mutableVar = 100;
for (int i = 0; i <= 10; ++i) mutableVar += i;

mutableVar는 여러 번 수정되는 가변 객체로 다뤄지기 때문에 지역 변수를 변경할 수 없다는 규칙에 위배된다.

int mutableVar = 100;

int mutableVar0 = mutableVar + 0;
int mutableVar1 = mutableVar0 + 1;
...
int mutableVar10 = mutableVar9 + 10;

모양새가 웃기긴 하지만 모든 변수들은 초기화 이후 수정되지 않았기 때문에 불변 객체이다.

함수에 전달된 인수 수정하기

함수에 값으로 전달된 인수는 복사본이 전달된 것이라서 원본이 변하지 않는다.

만약 원본을 수정하고 싶다면 참조를 전달하면 되고, 데이터를 직접 참조로 넘기기보다는 데이터를 담은 클래스나 구조체를 넘겨서 수정하는 것이 더 좋다.

값 수정 금지하기

불변성의 핵심 요소는 값 수정을 막는 것이다.

class MyAge {
public:
    const int age;
    MyAge(cosnt int initAge = 20) : age(initAge) {}
};

MyAge ageNow, ageLater(8);
ageNew.age = 10; // error

const 키워드를 사용하면 값의 수정을 막을 수 있다.

const 키워드는 함수 동작에 불변성을 제공해줌과 동시에 클래스 안의 변수가 수정되지 않음을 확신할 수 있다.

불변 객체에 일급 함수와 순수 함수 적용하기

class MyValue {
public:
    const int value;
    MyValue(int v) : value(v) {}
};

class MyFunction {
public:
    const int x, y;
    MyFunction(int _x, int _y) : x(_x), y(_y) {}
    MyValue addition() const { ... } // 순수 함수
    MyValue subtraction() const { ... }
    MyValue multiplication() const { ... }
    MyValue division() const { ... }
};

int a = 100;
int b = 10;

MyFunction func(a, b); // 객체 생성

 /* 멤버 함수 객체(std::function) 생성. 일급 함수 */
auto callableAdd = std::mem_fn(&MyFunction::addition);
auto callableSub = std::mem_fn(&MyFunction::subtraction);
auto callableMul = std::mem_fn(&MyFunction::multiplication);
auto callableDiv = std::mem_fn(&MyFunction::division);

/* 멤버 함수 호출 */
auto value1 = callableAdd(func);
auto value2 = callableSub(func);
auto value3 = callableMul(func);
auto value4 = callableDiv(func);

std::mem_fn 함수로 MyFunction 클래스의 멤버 함수를 일급 함수로 만든다.

각 멤버 함수들은 동일한 입력에 대해 항상 같은 결과를 반환하는 순수 함수이고 MyValue의 value는 const로 선언되어서 값을 변경할 수 없다.

불변 객체 구현하기

가변 객체 만들기

클래스의 일반적인 형태로 멤버 변수는 private, 접근 함수(get/set)를 public으로 선언하는 경우 OOP 규칙은 준수되지만 인스턴스화 된 이후에도 값이 언제나 수정될 수 있기 때문에 가변적이다.

가변 객체를 불변 개체로 변환하기

멤버 변수와 함수에 const 키워드를 부여하고 set 함수를 제거함으로써 불변성을 부여한다.

다만 이런식으로 불변성을 부여하게 되면 멤버 변수를 수정할 수 있는 방법이 없다.

값을 수정하면서 불변성을 유지하는 방법중에 새로운 인스턴스를 생성하고 반환하는 방법이 있다.

class ImmutableEmployee {
public:
    ImmutableEmployee(const int& id, const std::string& firstName, ...)
    : m_id(id), m_firstName(firstName), ... {}
    const ImmutableEmployee SetId(const int& id) const {
        return ImmutableEmployee(id, m_firstName, ...); // 새로운 인스턴스를 반환한다
    }
    ...
private:
    const int m_id;
    const std::string m_firstName;
    ...
};

ImmutableEmployee me(0, first, last, d);

ImmutableEmployee me2 = me.SetId(1);
ImmutableEmployee me3 = me.SetFirstName("Alexis");
...

맨 처음 모양새가 웃기다고 했었던 코드와 매우 유사한 형태를 띈다.

추가로 읽기용 함수는 값 대신 const 참조를 반환하는것이 좋다.

불변성의 장점

함수형 프로그래밍의 핵심 요소는 불변 객체이다. 불변 객체를 통해 얻을 수 있는 이득은 다음과 같다.

◾ 외부 상태가 변경되지 않으므로 부작용을 없앨 수 있다. 만약 변경이 필요하다면 새로운 객체 인스턴스를 생성해서 객체 내부의 값을 수정할 수 있다.

◾ 잘못된 객체 상태가 존재하지 않는다. 왜냐면 현재 객체의 상태를 바꾸는게 아니라 변경할 값으로 새로운 객체를 만들기 때문이다.

◾ 잠금없이 여러 개의 함수를 함께 실행할 수 있기 때문에 스레드에 안전하다(thread-safe). 즉, 동기화 이슈를 피할 수 있다.

순수 함수로 부작용 피하기

함수 내에서 전역 변수 등 외부의 변수를 참조하지 않기 때문에 외부 상태를 변경하는 부작용이 발생하지 않는다.

float circleArea(float r)
{
    return 3.14f * r * r;
}

float f = 2.5f; // 지역 변수
for (int i = 1; i <= 5; ++i) circleArea(f);

동일한 입력에 대해 항상 같은 값을 출력하므로 circleArea는 순수 함수이다.

int currentState = 0; // 전역 변수

int increment(int i)
{
    currentState += i;
    return currentState;
}

int fix = 5; // 지역 변수
for (int i = 1; i <= 5; ++i) increment(fix);

increment는 매번 다른 값을 반환할 뿐만 아니라 함수 외부의 전역 변수에 의존하므로 순수 함수가 아니다.

float phi = 3.14f; // 전역 변수

float circleArea(float r)
{
    return phi * r * r;
}

float f = 2.5f; // 지역 변수
for (int i = 1; i <= 5; ++i) circleArea(f);

circleArea는 매번 같은 값을 반환하지만 함수 외부의 전역 변수를 참조하기 때문에 순수 함수가 아니다.

추가로 함수에 의해 변경되는 전역 변수나 참조자의 상태뿐만 아니라 화면 출력, I/O 연산 등의 IPC 역시 부작용에 포함된다.

커링으로 함수 분리하기

template<typename Func, typename... Args>
auto curry(Func func, Args... args)
{
    return [=](auto... lastParam) {
        return func(args..., lastParam...);
    };
}

int areaOfRectangle(int length, int width)
{
    return legnth * width;
}

auto length5 = curry(areaOfRectangle, 5);

for (int i = 0; i <= 5; ++i) std::cout << length5(i) << '\n';
/* length5(i) == areaOfRectangle(5, i); */

다수의 인자를 받는 함수를 단일 인자를 받는 함수로 줄인 코드이다.

auto multiply2(int a)
{
    return [=](int b) {
        return a * b;
    };
}

auto multiply3(int a)
{
    return [=](int b) {
        return multiply2(a * b);
    };
}

std::cout << multiply3(5)(10)(2) << '\n';

이런 식으로도 사용 가능하다.

고차 함수의 세 가지 기능

일급 함수와 고차 함수의 개념은 매우 유사하지만 일급 함수는 언어적 특성이고 고차 함수는 개별 함수의 특성이라는 차이가 있다.

"C++는 일급 함수를 지원한다" → 언어가 범위. 언어 차원에서 일급 함수를 지원하는지 여부를 따진다.

"xyz() 함수는 고차 함수다" → 함수가 범위. xyz() 함수가 고차 함수인지 여부를 따진다.

고차 함수의 특성, 맵 알아보기

std::map이 아니라 고차 함수 특징으로의 맵을 말한다.

어떤 컨테이너의 각 요소에 함수를 적용하여 동일한 순서의 새로운 컨테이너를 만드는 것이다.

std::vector<int> v1 = { 1, 2, 3, 4, 5 };
std::vector<int> v2;
v2.resize(v1.size());

/* v1을 사용해 새로운 컨테이너 v2를 만들어낸다 */
std::transform(std::begin(v1), std::end(v1), std::begin(v2),
    [](int i) { return i * i; });

std::cout << "v1 contains:";
for (auto v : v1) std::cout << " " << v;
std::cout << '\n';

std::cout << "v2 contains:";
for (auto v : v2) std::cout << " " << v;
std::cout << '\n';

함수가 인자로 넘겨졌으며 넘겨진 함수에 의해 동일한 작업이 수행되어 새로운 컨테이너가 생성되었기 때문에 std::transform은 맵이다.

고차 함수의 특성, 필터로 데이터 추출하기

기존 데이터 구조에 bool 값을 반환하는 조건을 적용하고 일치하는 요소들만 추려내어 새 데이터 구조를 만드는 것이다.

std::vector<int> numbers = { 0, 1, .., 19 };
std::vector<int> primes;

/* numbers에서 소수만 필터링하여 primes에 추가한다 */
std::copy_if(std::begin(numbers), std::end(numbers), std::back_inserter(primes),
    [](int n) {
        if (n < 2) {
            return (n != 0) ? true : false;
        }
        else {
            for (int j = 2; j < n; ++j) {
                if (n % j == 0) return false;
            }
        return true;
        }
    });

함수가 인자로 넘겨졌으며 넘겨진 함수의 반환된 bool값에 의해 새로운 컨테이너가 생성되었기 때문에 std::copy_if는 필터이다.

고차 함수의 특성, 폴드 알아보기

데이터 구조를 하나의 값으로 줄이는 기술을 말한다.

폴드는 왼쪽부터 결합하는 왼쪽 폴드와 오른쪽부터 결합하는 오른쪽 폴드 두 가지 타입이 있다.

((((0 + 1) + 2) + 3) + 4) // 왼쪽 폴드 foldl
(0 + (1 + (2 + (3 + 4)))) // 오른쪽 폴드 foldr

int addition(const int& x, const int& y)
{
    std::cout << x << " + " << y << '\n';
    return x + y;
}

std::vector<int> numbers = { 0, 1, 2, 3, 4 };

std::cout << "foldl" << '\n';
auto foldl = std::accumulate(std::begin(numbers), std::end(numbers), 0, addition); // 10
std::cout << '\n' << "foldr" << '\n';
auto foldr = std::accumulate(std::rbegin(numbers), std::rend(numbers), 0, addition); // 10

순방향 이터레이터를 사용하면 foldl, 역방향 이터레이터를 사용하면 foldr이 되고 컨테이너의 요소들이 누적합으로 계산되어 하나의 값으로 줄어들었기 때문에 std::accumulate는 폴드이다.

일급 함수

한마디로 변수처럼 다룰 수 있는 함수를 의미한다.

다른 함수의 매개변수로 함수 전달

typedef std::function<int(int, int)> FuncType; // 함수 객체 타입 재정의

int addition(int x, int y) { ... }
int subtraction(int x, int y) { ... }
int multiplication(int x, int y) { ... }
int division(int x, int y) { ... }
void PassingFunc(FuncType fn, int x, int y) { ... }

...
switch (i) {
    case 1: PassingFunc(addition, a, b); break;
    case 2: PassingFunc(subtraction, a, b); break;
    ...
}

함수의 매개 변수로 함수(함수객체)가 전달되어 동작이 다르게 실행된다.

변수에 함수 대입

typedef std::function<int(int, int)> FuncType; // 함수 객체 타입 재정의

...

FuncType func;

switch (i) {
    case 1: func = addition; break;
    case 2: func = subtracion; break;
    ...
}

std::cout << "Result = " << func(a, b) << '\n';

함수 객체를 변수로 만들어서 조건에 따라 함수를 대입하고 이후 함수 호출하듯이 사용하면 된다.

컨테이너에 함수 저장

typedef std::function<int(int, int)> FuncType;

std::vector<FuncType> functions;

functions.push_back(addition);
functions.push_back(subtraction);
...
std::cout << "Result = " << function.at(i - 1)(a, b) << '\n';

런타임에 새로운 함수 생성

typedef std::function<double(double)> HyperbolicFunc; // 함수 객체 타입 재정의

std::vector<HyperbolicFunc> funcs = {
    sinh, cosh, tanh, [](double x) { return x*x; }
};
std::vector<HyperbolicFunc> inverseFuncs = {
    asinh, acosh, atanh, [](double x) { return exp(log(x) / 2); }
};

template <typename A, typename B, typename C>
std::function<C(A)> compose(std::function<C(B)> f, std::function<B(A)> g)
{
    return [f, g](A x) { return f(g(x)) };
}


std::vector<HyperbolicFunc> composedFuncs; // 합성 함수가 저장될 컨테이너
std::vector<double> nums;
for (int i = 1; i <= 5; ++i) nums.push_back(i * 0.2);

/* 이항 함수 연산 */
std::transform(std::begin(inverseFuncs), std::end(inverseFuncs),
    std::begin(funcs), std::back_inserter(composedFuncs),
    compose<double, double, double>);

for (auto num : nums) {
    for (auto func : composedFuncs) {
        std::cout << "f(g(" << num << ")) = " << func(num) << '\n';
    }
}

함수 템플릿은 컴파일 타임에 평가되지만 반환값인 함수 객체는 런타임에 생성된다.