Editing Functional programming (section)

=== Recursion ===
{{Main|Recursion (computer science)}}

[[Iteration]] (looping) in functional languages is usually accomplished via [[recursion]]. [[recursion (computer science)|Recursive functions]] invoke themselves, letting an operation be repeated until it reaches the [[Recursion (computer science)|base case]]. In general, recursion requires maintaining a [[Call stack|stack]], which consumes space in a linear amount to the depth of recursion. This could make recursion prohibitively expensive to use instead of imperative loops. However, a special form of recursion known as [[tail recursion]] can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. Tail recursion optimization can be implemented by transforming the program into [[continuation passing style]] during compiling, among other approaches.

The [[Scheme (programming language)|Scheme]] language standard requires implementations to support proper tail recursion, meaning they must allow an unbounded number of active tail calls.<ref name='SchemeProperTailRec'>{{cite web|url=http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11 |title=Revised^6 Report on the Algorithmic Language Scheme |publisher=R6rs.org |access-date=2013-03-21}}</ref><ref>{{cite web|url=http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3 |title=Revised^6 Report on the Algorithmic Language Scheme - Rationale |publisher=R6rs.org |access-date=2013-03-21}}</ref> Proper tail recursion is not simply an optimization; it is a language feature that assures users that they can use recursion to express a loop and doing so would be safe-for-space.<ref>{{cite book|chapter=Proper tail recursion and space efficiency|last=Clinger|first=William|title=Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation - PLDI '98|date=1998|pages=174–185|doi=10.1145/277650.277719|isbn=0897919874|s2cid=16812984}}</ref> Moreover, contrary to its name, it accounts for all tail calls, not just tail recursion. While proper tail recursion is usually implemented by turning code into imperative loops, implementations might implement it in other ways. For example, [[Chicken (Scheme implementation)|Chicken]] intentionally maintains a stack and lets the [[stack overflow]]. However, when this happens, its [[Garbage collection (computer science)|garbage collector]] will claim space back,<ref>{{cite web |url=http://home.pipeline.com/~hbaker1/CheneyMTA.html |title=CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. |last=Baker |first=Henry |date=1994 |access-date=2020-04-29 |archivedate=2006-03-03 |archiveurl=https://web.archive.org/web/20060303155622/http://home.pipeline.com/~hbaker1/CheneyMTA.html |url-status=deviated }}</ref> allowing an unbounded number of active tail calls even though it does not turn tail recursion into a loop.

Common patterns of recursion can be abstracted away using higher-order functions, with [[catamorphism]]s and [[anamorphism]]s (or "folds" and "unfolds") being the most obvious examples. Such recursion schemes play a role analogous to built-in control structures such as [[Program loops|loops]] in [[imperative languages]].

Most general purpose functional programming languages allow unrestricted recursion and are [[Turing complete]], which makes the [[halting problem]] [[undecidable problem|undecidable]], can cause unsoundness of [[equational reasoning]], and generally requires the introduction of [[inconsistency]] into the logic expressed by the language's [[type system]]. Some special purpose languages such as [[Coq (software)|Coq]] allow only [[well-founded]] recursion and are [[strongly normalizing]] (nonterminating computations can be expressed only with infinite streams of values called [[codata (computer science)|codata]]). As a consequence, these languages fail to be Turing complete and expressing certain functions in them is impossible, but they can still express a wide class of interesting computations while avoiding the problems introduced by unrestricted recursion. Functional programming limited to well-founded recursion with a few other constraints is called [[total functional programming]].<ref name=totalfp>{{cite journal |last=Turner |first=D.A.|author-link=David Turner (computer scientist) |title=Total Functional Programming |journal=Journal of Universal Computer Science|volume=10| date=2004-07-28 |pages=751–768 |url=http://www.jucs.org/jucs_10_7/total_functional_programming|doi=10.3217/jucs-010-07-0751|issue=7}}</ref>