https://www.explainxkcd.com/wiki/api.php?action=feedcontributions&user=208.191.157.18&feedformat=atomexplain xkcd - User contributions [en]2024-03-29T14:49:32ZUser contributionsMediaWiki 1.30.0https://www.explainxkcd.com/wiki/index.php?title=1270:_Functional&diff=496331270: Functional2013-09-27T18:53:13Z<p>208.191.157.18: improved the english explanation of recursion and tail recursion (contact: https://twitter.com/f06io)</p>
<hr />
<div>{{comic<br />
| number = 1270<br />
| date = September 26, 2013<br />
| title = Functional<br />
| image = functional.png<br />
| titletext = Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|1270: Functional}}<br />
<br />
[[White Hat]] questions [[Cueball]]'s faith in {{w|functional programming}}. [[Cueball]] responds saying, "Tail recursion is its own reward."<br />
<br />
In computer science, recursion is when a function invokes itself with arguments representing a smaller computation than the current invocation received. Eventually, the computation is small enough to require no further recursive invocations. In this way, recursion effects a standard loop in a program.<br />
<br />
For example, the {{w|factorial}} function can be coded as:<br />
<br />
factorial(n):<br />
if n == 0:<br />
return 1<br />
else:<br />
return n * factorial(n - 1)<br />
<br />
{{w|Tail recursion}} is a special case of recursion in which the environment of the current invocation is not preserved when the recursive invocation occurs. Not all programming languages implement tail recursion because it is considered by some to be an optimization. To allow tail recursion to occur in a language which implements it, the function must immediately return the result of the recursive invocation. No subsequent computation may occur in the current invocation.<br />
<br />
If these circumstances are met, a compiler may simply arrange for the recursive call to jump to the start of the function with modified arguments. This effectively turns a recursive call into an iterative loop, whilst retaining the simplicity of a recursive call.<br />
<br />
The first example of "factorial" shown above is not tail recursive because the multiplication operation cannot be evaluated until after the recursive invocation. This example is tail recursive inside the helper function.<br />
<br />
factorial(n):<br />
return factorial_helper(n, 1)<br />
<br />
factorial_helper(n, acc):<br />
if n == 0:<br />
return acc<br />
else:<br />
return factorial_helper(n - 1, n * acc)<br />
<br />
The technique used here is to use a helper function with an additional argument called an accumulator which will accumulate results from previous calls to the function. It is often used to implement tail recursive or iterative versions of recursive functions. This is not applicable for all recursive functions, though.<br />
<br />
<br />
Cueball is making the pun that "(functional programming) is an end unto itself", which would be both figuratively and literally correct.<br />
<br />
<br />
The title text describes that to {{w|Abstract mathematics|abstract mathematicians}} functional programming is both powerful and flexible, as well as intuitive and clear since it comes very close to the way mathematicians usually describe functions. On the other hand to non-mathematicians, functional programming can be exactly the opposite (thus being non-intuitive and unclear as abstract mathematics appears to them).<br />
<br />
The title text is also a reference to a common saying about C (An {{w|Imperative programming|imperative programming}} language): "C combines the flexibility and power of assembly language with the user-friendliness of assembly language".<br />
<br />
==Transcript==<br />
:[White Hat stands behind Cueball, who is sitting at a computer]<br />
:White Hat: Why do you like functional programming so much? What does it actually ''get'' you?<br />
:Cueball: Tail recursion is its own reward.<br />
<br />
{{comic discussion}}<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Programming]]<br />
[[Category:Recursion]]</div>208.191.157.18