| Latest revision |
Your text |
| Line 1: |
Line 1: |
| | Am i the only one considering this can be presented also in opposition to Object Oriented Programming, where tail recursion is very difficult to achieve at execution time, and impossible to achieve at compilation time, due to the possibility of method overloading?[[Special:Contributions/193.190.231.132|193.190.231.132]] 15:17, 30 September 2013 (UTC) | | Am i the only one considering this can be presented also in opposition to Object Oriented Programming, where tail recursion is very difficult to achieve at execution time, and impossible to achieve at compilation time, due to the possibility of method overloading?[[Special:Contributions/193.190.231.132|193.190.231.132]] 15:17, 30 September 2013 (UTC) |
| − | :Since tail recusion is special case of tail call you don't need to know where the last function called goes - you just replace call by jump - if you don't know where by indirect jump. AFAIK both clang and gcc are doing it and in FP this gives the 'continuation passing style' of programming. The problem with it is that you loose the stacktrace so usually it is done only for optimized builds. [[Special:Contributions/199.27.130.234|199.27.130.234]] 06:41, 26 October 2014 (UTC)
| |
| | | | |
| | I'm getting the adblock message at the top.. on mobile. On an unrelated note, I laughed and I don't even get it. Edit: I'm also seeing an ad while seeing the message.[[Special:Contributions/50.159.5.112|50.159.5.112]] 06:03, 27 September 2013 (UTC) | | I'm getting the adblock message at the top.. on mobile. On an unrelated note, I laughed and I don't even get it. Edit: I'm also seeing an ad while seeing the message.[[Special:Contributions/50.159.5.112|50.159.5.112]] 06:03, 27 September 2013 (UTC) |
| Line 7: |
Line 6: |
| | I removed that misguided explanation about lists that was not tail recursive. I'm also wondering if we should also mention that tail call optimization is also applicable to mutually recursive functions. In fact proper functional languages will always apply it whether the functions are recursive or not. Maybe emphasize the fact that "The efficiency and elegance are the literal rewards of tail recursion."? | | I removed that misguided explanation about lists that was not tail recursive. I'm also wondering if we should also mention that tail call optimization is also applicable to mutually recursive functions. In fact proper functional languages will always apply it whether the functions are recursive or not. Maybe emphasize the fact that "The efficiency and elegance are the literal rewards of tail recursion."? |
| | | | |
| − | I feel like the examples should be in Haskall[sic], because that is the major functional language... [[Special:Contributions/67.160.98.42|67.160.98.42]] 09:48, 27 September 2013 (UTC) GBGamer117 | + | I feel like the examples should be in Haskall, because that is the major functional language... [[Special:Contributions/67.160.98.42|67.160.98.42]] 09:48, 27 September 2013 (UTC) GBGamer117 |
| − | :I think {{w|Haskell (programming language)|Hask'''e'''ll}} is more common, but I agree. And to emphasize the clarity, usually if/else blocks are avoided using pattern matching. I.e. tail-recursive factorial can be written as follows: | + | :I think Hask'''e'''ll is more common, but I agree. And to emphasize the clarity, usually if/else blocks are avoided using pattern matching. I.e. tail-recursive factorial can be written as follows: |
| | fac2::Integer->Integer-> Integer -- optional function header | | fac2::Integer->Integer-> Integer -- optional function header |
| | fac2 acc 0 = acc | | fac2 acc 0 = acc |
| Line 79: |
Line 78: |
| | :::There is no agreement yet, if and when we should introduce/''explain'' the concept of functional programming. At the moment the transition is very abrupt, partly because someone changed my first functional example to imperative code. The tail recursive example is at this very moment exactly the same as [http://ideone.com/OrCUMp this valid functional code (written in Haskell)]. --[[User:Chtz|Chtz]] ([[User talk:Chtz|talk]]) 21:07, 30 September 2013 (UTC) | | :::There is no agreement yet, if and when we should introduce/''explain'' the concept of functional programming. At the moment the transition is very abrupt, partly because someone changed my first functional example to imperative code. The tail recursive example is at this very moment exactly the same as [http://ideone.com/OrCUMp this valid functional code (written in Haskell)]. --[[User:Chtz|Chtz]] ([[User talk:Chtz|talk]]) 21:07, 30 September 2013 (UTC) |
| | ::::I agree, this is still chaos! Please explain "An imperative, recursive (but not tail-recursive) implementation can look like this:", I disagree and there is still no prove helping me or other people to understand. And beside: My first recursive program was to solve a one player game, written in {{w|Turbo Pascal}} in the middle of the eighties of the last century. And it was ''fast'' even at that time. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 21:47, 30 September 2013 (UTC) | | ::::I agree, this is still chaos! Please explain "An imperative, recursive (but not tail-recursive) implementation can look like this:", I disagree and there is still no prove helping me or other people to understand. And beside: My first recursive program was to solve a one player game, written in {{w|Turbo Pascal}} in the middle of the eighties of the last century. And it was ''fast'' even at that time. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 21:47, 30 September 2013 (UTC) |
| − | :::::I guess you mostly disagree on the non tail-recursiveness? Basically, this can be seen as the recursion can't be replaced by a simple replacement of the return statement with another function call, because after the call another operation (the multiplication by n) needs to be performed before the value can be returned. My original attempt on this article was to switch to functional programming at this point, since it does not make much sense to implement such a simple function recursively in an imperative language (admittedly, the transition to functional programming was way to abrupt). When implementing a function which searches inside a tree it often/usually makes sense to implement it recursively even in imperative languages and with some tricks you can also make this comparatively fast (I assume that was the point of your last two sentences?). To come back to 178.98... My intention was to structure the explanation approximately as follows:
| |
| − | :::::1) Describe the difference between functional and imperative programming (assuming that most readers know what imperative programming is -- if we can't assume that, where shall we start?)
| |
| − | :::::2) Give an example of a simple imperative function (e.g. the factorial function) written with typical imperative constructs (loops, assignments)
| |
| − | :::::3) As this is not possible in functional programming introduce the concept of recursion and define the function recursively (this step was clearly to fast)
| |
| − | :::::4) Explain the benefit of tail-recursion and give an tail-recursive example of factorial (also in functional programming)
| |
| − | :::::5) '''Explain the actual joke!'''
| |
| − | :::::6) Explain remaining parts (title text, ...) --[[User:Chtz|Chtz]] ([[User talk:Chtz|talk]]) 22:41, 30 September 2013 (UTC)
| |
| − | ::::::On your fourth point, the functional programming example is confusing, and strange. Why are you defining two seperate functions, when a single function would do? For example, an easy way to show this is:
| |
| − | factorial[0] = 1
| |
| − | factorial[n] = n * factorial(n - 1)
| |
| − | ::::::which, though not valid computer code, is valid mathematical syntax, and shows perfectly what a factorial function, in functional programming, does. The explanation would then be:
| |
| − | factorial[6] = 6 * factorial[6-1] = 6 * 120 = 720
| |
| − | factorial[5] = 5 * factorial[5-1] = 5 * 24 = 120
| |
| − | factorial[4] = 4 * factorial[4-1] = 4 * 6 = 24
| |
| − | factorial[3] = 3 * factorial[3-1] = 3 * 2 = 6
| |
| − | factorial[2] = 2 * factorial[2-1] = 2 * 1 = 2
| |
| − | factorial[1] = 1 * factorial[1-1] = 1 * 1 = 1
| |
| − | factorial[0] = 1
| |
| − | ::::::or something similar to that. [[User:GBGamer117|GBGamer117]] ([[User talk:GBGamer117|talk]]) 05:07, 2 October 2013 (UTC)
| |
| − | :::::::I would be totally fine (and originally intended) to have this definition at step 3). If you replace your [ ] brackets by ( ) parentheses, or leave them, [http://ideone.com/1ZWZ9T it is actually valid Haskell code] (and as you point out, [clear and intuitive as] ''valid mathematical syntax''). The evaluation, however would rather go like:
| |
| − | factorial(4) = 4 * factorial(3)
| |
| − | = 4 * ( 3 * factorial (2) )
| |
| − | = 4 * ( 3 * ( 2 * factorial (1) ) )
| |
| − | = 4 * ( 3 * ( 2 * ( 1 * factorial (0) ) ) )
| |
| − | = 4 * ( 3 * ( 2 * ( 1 * 1 ) ) )
| |
| − | = 4 * ( 3 * ( 2 * 1 ) ) = 4 * ( 3 * 2 ) = 4 * 6 = 24
| |
| − | :::::::That would actually give a nice example, why this recursion is less efficient than actual tail recursion: During evaluation, you need to build up an entire expression tree which you don't have to do for the tail-recursive way (it does not really matter for this simple function, though).
| |
| − | factorial(4) = factorial_helper(4, 1) = factorial_helper(3, 4) = factorial_helper(2, 12) = factorial_helper(1, 24) = factorial_helper(0, 24) = 24
| |
| − | :::::::The number of numerical operations is actually the same (I omitted the steps of evaluating the products and differences), but you don't have to build up a large expression, before you can actually start multiplying. --[[User:Chtz|Chtz]] ([[User talk:Chtz|talk]]) 07:51, 2 October 2013 (UTC)
| |
| − |
| |
| − | ;Tail Recursion?
| |
| − |
| |
| − | Are we really certain "tail recursion" isn't also an innuendo for ongoing sexual relations? Tail is sometimes used as slang, and if it were received regularly, it would be tail recursion.{{unsigned ip|69.67.112.5}}
| |
| − |
| |
| − | ;Explain the concept, not the history?
| |
| − |
| |
| − | I think that this page would benefit from simplifying the beginning to explain the concept without providing all of the background. Background can be applied later. I would suggest this:
| |
| − |
| |
| − | :Recursion is a common programming practice where a function calls itself. This can result in many layers of the function, all of which need to be kept track of until the program can get to the bottom layer. The last step of this process is to return the final value through all of the layers of function calls.
| |
| − |
| |
| − | :If there is nothing left for a function to do when the lower level returns, then there is no longer a need to keep track of the state of that layer. Instead of creating a new layer, a compiler that is smart enough can overwrite the existing layer with the new layer. This means that the new layer will pass its results directly to whatever initially called the function and not have to waste time passing the results up the stack of function calls. Making use of this optimization is called ''tail recursion'', and it saves both time and memory requirements.
| |
| − |
| |
| − | :Functional programming is a programming language style that appeals to people who spend a lot of time staring at the notation used to describe higher math. This notation commonly uses recursion and formulas that include entire other formulas as variables in a higher level formula. Tail recursion was first introduced as a more efficient manner of handling recursion within functional programming languages, and they are currently the only programming languages that support this optimization.
| |
| − |
| |
| − | [[User:Mythobeast|Mythobeast]] ([[User talk:Mythobeast|talk]]) 21:07, 3 March 2014 (UTC)
| |
| − |
| |
| − | :Frankly, I don't think the point here is about what concept it is. Tail recursion is just one of the many peculiar aspects of functional programming that, frankly, does not make that much different in the long run. (Frankly, a loop is about 20 times easier than tail recursion in about 90% of the cases; same for passing functions around). However, those things are rewarding to play with in and of themselves (and who care about the long run anyway? In the long term, we are all dead). At least that how I think of this slide. [[User:magice|magice]] ([[User talk:magice|talk]])
| |
| − |
| |
| − | Maybe the long explanation should be a trivia item?[[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 21:59, 21 June 2014 (UTC)
| |
| − |
| |
| − | I've read all of the explanation and all of the comments as of now. In all of it, I found no mention of explaining what the optimization itself consists of. In case it is one day decided to add that explanation, I want to add my 2 cents and explain it here, as readable to non-programmers as I can:
| |
| − | "Computer programs are like cooking recipes: a ordered list of instructions. Usually, there are groups of instructions that are used regularly. To keep from copying and pasting these groups wherever they are needed, functions were created. When a computer executes a function, it jumps from the instruction it was executing to the first instruction of that function. When the function ends, the computer jumps back to the instruction that called the function (one after actually). Since functions can call other functions, the computer keeps a stack of function calls (and other things) to remember all the jumps it made. Think of it as a stack of heavy objects: usually, you can only move the topmost one. So, when the functions ends, the computer make the backward jumps in the reverse order they were stacked. A recursive function (explained above) may fill up the stack quickly. To avoid that, tail recursive functions (explained above) cause only the first function call to be stacked, no matter how many calls happen afterwards."
| |
| − | Also, out of topic but, with these comments, I found out that the editing box have a limit on how much you can stretch it downwards. [[Special:Contributions/108.162.219.148|108.162.219.148]] 18:58, 23 November 2014 (UTC)
| |
| − |
| |
| − | I just reinstated a removed word, but it looks (unintentionally?) complicated as it is. It was one of two consecutive "that"s in a sentence with two other "that"s in, and perhaps not enough commas, semicolons, hyphens, emdashes and/or parentheses. I.e. "Another explanation is that the fact that that part of the title text is confusing is a metaphor for the fact that abstract mathematics and functional programming can be confusing" (then a clause-break comma and even more words...). Breaking it down "(the fact that) (that part)" is roughly "(an interpretation of) (a detail)". Or, to put it another way, that that "that" that that "that that" lost was necessary. But confusing. [[Special:Contributions/172.70.85.177|172.70.85.177]] 06:25, 27 March 2022 (UTC)
| |
