Tail Recursion - F#에서는 recursion이 loop을 대체한다. (2)

이전 글: https://www.minigb.io/304

F#에서는 recursion이 loop을 대체한다.

 

 

 

고수의 도움을 받았다. 🤩 감사합니다!

Tail recursion에 관해 알아보았다.
아래는 챗지피티와의 대화에서 얻은 내용들입니다.

Tail Recursion

Tail recursion is a special case of recursion where the recursive call is the last operation in the function. This means that the function returns the result of its recursive call directly, without doing any more computations after that call. In other words, the final action of a tail-recursive function is to call itself, possibly with new arguments, but it does not process the return value of this call any further.

Here's why tail recursion is important:

1. Optimization
Many compilers and interpreters can optimize tail-recursive functions by converting them into a loop, thus avoiding the creation of a new stack frame for each recursive call. This optimization is known as tail call optimization (TCO). TCO reduces the risk of stack overflow errors in programs that would otherwise require deep recursion.
It can also improve performance by reducing the overhead associated with recursive calls.

2. Memory Efficiency

Because tail-recursive functions can be optimized into iterative loops, they can be more memory-efficient than their non-tail-recursive counterparts. This is especially important in languages and environments with limited stack space.

3. Functional Programming

Tail recursion is a key concept in functional programming languages, where loops are often expressed through recursion. Tail recursion makes it possible to write efficient loops in a functional style without the typical overhead associated with recursive function calls.

Here is a simple example to illustrate tail recursion:

 

def factorial(n, accumulator=1):
    if n == 0:
        return accumulator
    else:
        return factorial(n-1, n*accumulator)

In this example, the `factorial` function is tail-recursive because the recursive call to itself is the last operation performed in the function. The result of the recursive call is returned directly. The `accumulator` parameter is used to keep track of the intermediate results of the factorial computation. This design allows the function to be optimized by compilers that support tail call optimization, making it efficient even for large values of `n`.

Not all programming languages or compilers support tail call optimization, but where it is supported, tail recursion can be a powerful tool for writing clean, efficient, and memory-safe recursive functions.

 

 

-
새롭게 알게된 건
1. recursion으로 loop을 대체하는 것은 functional programming language의 특징이다. F#만의 특징이 아니다.
2. loop을 recursion으로 대체하는 것은 recursion 중에서도 tail recursion에 더 가깝다. non-tail recursion에서는 recursive function call의 return 값이 연산에 사용되지만, tail recursion에서는 그렇지 않기 때문에 연산의 결과를 저장하는 변수 (위 코드에서는 accumulator)가 따로 필요하고, 이는 loop과 비슷한 특징이다.

 

long long factorial_with_non_tail_recursion(long long n) {
    if (n == 0) {
        return 1;
    }
    else {
        return n * factorial_with_non_tail_recursion(n - 1);
    }
}

long long factorial_with_tail_recursion(long long n, long long accumulator = 1) {
    if (n == 0) {
        return accumulator;
    }
    else {
        return factorial_with_tail_recursion(n - 1, n * accumulator);
    }
}

long long factorial_with_loop(long long n) {
    long long result = 1;

    for (long long i = n; i >= 1; i--) {
        result *= i;
    }

    return result;
}

그렇다면 굳이 recursion으로 loop을 대체하는 이유는?

The use of recursive functions to replace loops in F# (and in functional programming languages more broadly) is rooted in several characteristics and philosophies of functional programming, rather than being a feature unique to F#. This approach stems from the functional programming paradigm's emphasis on immutability, statelessness, and expressions over statements. Let's explore how these contribute to the preference for recursion:

1. Immutability and Statelessness

Functional programming languages encourage the use of immutable data structures and stateless functions. Loops, by their nature, involve mutable state; a loop counter is incremented or changed with each iteration, for example. Recursion, on the other hand, can easily operate without altering any external state, fitting well with the principles of immutability and statelessness.

2. Expressions Over Statements

Functional programming often favors expressions over statements. Expressions evaluate to a value and can be easily composed with other expressions. Loops are typically statements that don't return a value and are used to perform actions. Recursion, being an expression, fits naturally into the functional style, allowing for elegant composition and reuse.

3. Higher-Level Abstraction

Recursive functions can provide a more abstract and declarative approach to defining the behavior of a program. Instead of describing how something should be done (as with loops), recursion allows programmers to define what should be achieved, letting the function's structure express the computation's logic more directly.

4. Tail Call Optimization (TCO)

Functional programming languages, including F#, often optimize tail-recursive functions by converting them into loops internally, thus avoiding the common drawbacks of recursion, such as stack overflow errors and inefficient memory usage. This optimization is a key feature that mitigates the performance concerns associated with recursion. It's worth noting that not all programming languages support TCO, but it is a common feature in those that heavily utilize recursion, including many functional languages.

The preference for recursion over loops in F# and other functional programming languages is not an arbitrary choice but rather a reflection of the paradigm's core principles. While recursion can indeed be less efficient in languages or environments that don't support tail call optimization, in those that do, such as F#, the performance difference is often negligible, and the benefits in terms of readability, immutability, and functional purity are significant.

 

으악… 정리하려고 하면 정보가 손실돼서 그냥 그대로 가지고 왔다.

신기하네. 교수님께서 수업 때 functional programming language를 접하고 나면 반응이 반으로 나뉜다고, 아주 좋아하게 될 수도 있고, 아니면 너무 낯설어서 싫어하게 될 수도 있다고 하셨는데. 아직 더 해봐야겠지만 아무튼 참 묘한 매력이 있다.

그리고 또 지나가던 고수분 의견이나 찾아보면 좋을 만한 거 있으시면 알려주세요!
제가 어느 정도 완벽히 숙지하고서 글을 쓰는 것도 좋겠지만, 그 전에 새롭게 알게 된 걸 우선 조금씩 공유하고, 그걸 통해 새로운 의견을 받고 추가하면서 디벨롭 해가는 게 더 효율적이고 좋은 방향인 거 같아서 우선 올리게 되었습니다.
새로운 정보 언제든지 환영입니다!

 

 

 

https://blog.naver.com/mini_gb/223387720650

Tail Recursion - F#에서는 recursion이 loop을 대체한다. (2)