앞서 확인한 개요에서 언급했는데 함수형 프로그래밍에선 반복을 재귀를 통해서 구현한다고 했는데 재귀와 꼬리재귀에 대해서 간단히 알아보자.

재귀

함수 본문에서 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 부른다. 재귀는 다른 명령어가 방지할 때까지 계속된다.

예제

꼬리 재귀 최적화 in python

재귀호출의 경우 호출 스택의 깊이가 얕은 경우엔 큰 상관이 없으나 깊이가 깊어지면 오버플로우가 발생하는 문제가 있다.
여담으로 실행하는 시스템에 따라서 조금씩 다를수 있지만 파이썬에서 호출가능한 스택의 최대 깊이는 보통 1000 정도에서 RecursionError가 발생한다.

이를 해결하기 위한 방법으로 제시되는 해결책 중 하나가 꼬리 재귀Tail recursion이다.

간단히 말하자면 함수에서 마지막으로 호출하는 함수가 자기 자신이고, 재귀 호출의 값을 반환받은후 추가적인 연산이 필요하지 않는 방식을 말한다.

꼬리 재귀 적용 예제

위의 예제에서 사용한 팩토리얼 함수를 보자.

fact(n)을 호출했을 때 연산이 끝나지 않았는데 fact(n-1)을 호출하기 때문에 리턴 주소를 저장하기 위해서 시스템 콜스택을 사용하게 된다.

즉, 현재 함수(fact(n))에서 결과값을 반환하기 위해서는 현재 함수의 인자 값(n)을 스택에 가지고 있다가 그 다음 호출될 함수(fact(n-1))의 결과 값과 함께 연산을 해야 한다는 점이다.
이러한 방식은 꼬리 재귀를 만족하지 못한다고 본다.

예제를 꼬리 재귀로 바꾸려면 어떻게 해야할까? 재귀를 호출하는 부분에서 추가적인 연산이 필요없도록 만들면 되는데

이를 구현하기 위해선

return에서는 (언어 스펙에서 지정한 스택에 메모리를 쌓지 않는 연산자를 제외한) 연산자를 사용하면 안된다.

연산자의 사용없이 재귀 호출의 반환값을 그대로 return 해주면 된다.

한가지 주의할 점은 개발자가 꼬리재귀 구조로 코드를 짜더라도 사용하는 언어의 스펙에 따라서 꼬리재귀 최적화 보장여부가 다르기 때문에 확인이 필요하다.
요즘 python을 공부하고 싶어서 위 예시를 python으로 들었지만 python은 꼬리재귀 최적화를 보장하지 않는데 python의 창시자 귀도 반 로섬의 의견은 다음과 같다.

귀도 반 로섬의 TRE(Tail Recursion Elimination)에 대한 반론

• 콜 스택을 추적하기에 부적합하다(디버깅이 어렵다)
• 단순 최적화기 때문에 개별 파이썬 컴파일러 구현체에서 선택하게 둘 것
• 재귀가 모든 것의 기반이라는 접근은 이상적인 수학적인 접근일 뿐이다
• 파이썬 스타일의 개발자들은 재귀 대신 멋진(?) 문법들을 쓸 수 있다
• not PYTHONIC 하다

Reference

tutorialspoint - Learn Functional Programming

재귀,반복, Tail Recursion

Tail Recursion Elimination

함수형~ 함수형~ 여러 곳에서 이야기는 종종 들었지만 제대로 찾아본 적이 없다보니 기본적인 개념부터 많이 부족해서 간단히 스터디를 시작했다.

특정 언어를 선정해서 언어적 특성에 종속되기 보단 우선 함수형 프로그래밍의 패러다임에 대해서 먼저 학습 해보자.

개요

함수형 프로그래밍은 크게 두 그룹으로 분류된다.

그럼 여기서 명령형은 뭐고 함수형 패러다임은 뭘 말하는 걸까?

프로그래밍 패러다임은 크게 보면 2가지로 분류할 수 있다.

1. 명령형 프로그래밍 : 프로그래밍의 상태와 상태를 변경시키는 구문의 관점에서 연산을 설명하여 기능을 구현하기 위한 알고리즘을 명시하지만 결국 무엇을 해야하는지는 명시하지 않는다.
   • 절차지향 프로그래밍 : 수행되어야 할 연속적인 계산 과정을 포함 (C, C++)
   • 객체지향 프로그래밍 : 객체들의 집합으로 프로그램의 상호작용을 표현 (C++, Java, C#)
2. 선언형 프로그래밍 : How(어떻게) 보단 What(무엇을) 해야하는지 설명하는 방식으로 알고리즘에 대해서 명시하진 않고 목표를 명시한다.
   • 함수형 프로그래밍 : 순수 함수를 조합하고 소프트웨어를 만드는 방식 (Clojure, Haskell, LISP)

명령형 프로그래밍은 어떻게 할 것이가(How)를 표현하고, 선언형 프로그래밍은 무엇을 할것인가(What)를 표현한다.

특성

함수형 프로그래밍은 아래와 같은 특징을 같는다.

• 계산을 수행하기 위해 조건식과 재귀를 사용하는 수학 함수의 개념에 따라 설계되었다.

• 고차함수high order function와 지연연산lazy evaluation 기능을 지원한다.

  1. 고차 함수

     • 람다 계산법에서 만들어진 용어로 아래 조건을 만족하는 함수
       • 함수에 함수를 파라미터로 전달할 수 있다.
       • 함수의 반환값으로 함수를 사용할 수 있다.
     • 고차 함수는 1급 함수의 부분집합이다.

  2. 지연 연산

     • 불필요한 연산을 피하기 위해서 결과값이 필요한 시점까지 연산을 늦추는 것을 말한다.
       • 값을 미리 계산해서 저장하지 않기 때문에 메모리의 효율적인 사용이 가능

• 루프문과 같은 흐름제어와 If-Else, Switch문과 같은 조건문을 지원하지 않고 함수와 함수호출을 직접 사용한다.

• OOP와 마찬가지로 추상화, 캡슐화, 상속, 다형성과 같은 개념을 지원한다.

장점

• Bugs-Free Code : State를 지원하지 않으므로 부작용이 없어서no side-effect 오류없는 코드작성이 가능하다.(없다기 보단 그냥 적은게 맞을 것 같다.)
• 효율적인 병렬 프로그래밍 : 상태 변경이 없기 때문에 병렬로 작동하도록 기능에 대해서 프로그래밍할 수 있으며 이는 재사용 및 테스트를 더 쉽게 지원한다.
• 효율성 : 독립적인 유닛으로 구성되서 동시에 실행할 수 있다.
• 중첩 함수 지원 : 중첩함수를 지원한다.
• 지연 연산 : Lazy List, Lazy Map 등과 같은 지연 함수 구조를 지원한다.

단점

• 큰 메모리 공간이 필요하며 상태가 없기 때문에 작업을 수행할 때마다 새 객체를 만들어야한다.

함수형 vs 객체지향

이상으로 함수형 프로그래밍에 대한 대략적인 개요에 대해서만 우선 정리해 보았다.

Reference

tutorialspoint - Lean Functional Programming

함수형 프로그래밍 요약

함수형 프로그래밍 언어에 대한 고찰