Tail recursion is an important performance optimisation stragegy in functional languages because it allows recursive calls to consume constant stack (rather than O(n)).

Are there any problems that simply cannot be written in a tail-recursive style, or is it always possible to convert a naively-recursive function into a tail-recursive one?

If so, one day might functional compilers and interpreters be intelligent enough to perform the conversion automatically?

Are there problems that cannot be written using tail recursion?

How do I break out a loop?

    var largest=0
    for(i&lt;-999 to 1 by -1) {
        for (j&lt;-i to 1 by -1) {
            val product=i*j
            if (largest&gt;product)
                // I want to break out here
            else
               if(product.toString.equals(product.toString.reverse))
                  largest=largest max product
        }
    }

How do I turn nested for loops into tail recursion?

From Scala Talk at FOSDEM 2009 http://www.slideshare.net/Odersky/fosdem-2009-1013261
on the 22nd page:

&gt; Break and continue
&gt; Scala does not have them. Why?
&gt; They are a bit imperative; better use many smaller functions
&gt; Issue how to interact with closures.
&gt; They are not needed!

What is the explanation?

  [1]: http://en.wikipedia.org/wiki/Project_Euler


How do I break out of a loop in Scala?

I have the following piece of code which fails with the following error:

&gt; RuntimeError: maximum recursion depth exceeded

I attempted to rewrite this to allow for tail recursion optimization (TCO). I believe that this code should have been successful if a TCO had taken place.

    def trisum(n, csum):
        if n == 0:
            return csum
        else:
            return trisum(n - 1, csum + n)
    
    print(trisum(1000, 0))

Should I conclude that Python does not do any type of TCO, or do I just need to define it differently?


Does Python optimize tail recursion?

Very simply, what is tail-call optimization?

More specifically, what are some small code snippets where it could be applied, and where not, with an explanation of why?


What is tail call optimization?

I&#39;m having major trouble understanding _recursion_ at school. Whenever the professor is talking about it, I seem to get it but as soon as I try it on my own it completely blows my brains. 

I was trying to solve _Towers of Hanoi_ all night and completely blew my mind. My textbook has only about 30 pages in recursion so it is not too useful. Does anyone know of books or resources that can help clarify this topic?

Understanding recursion

It seems to me that it would work perfectly well to do tail-recursion optimization in both C and C++, yet while debugging I never seem to see a frame stack that indicates this optimization. That is kind of good, because the stack tells me how deep the recursion is. However, the optimization would be kind of nice as well.

Do any C++ compilers do this optimization? Why? Why not?

How do I go about telling the compiler to do it?

 * For MSVC: `/O2` or `/Ox`
 * For GCC: `-O2` or `-O3`

How about checking if the compiler has done this in a certain case?

 * For MSVC, enable PDB output to be able to trace the code, then inspect the code
 * For GCC..?

I&#39;d still take suggestions for how to determine if a certain function is optimized like this by the compiler (even though I find it reassuring that Konrad tells me to assume it)

It is always possible to check if the compiler does this at all by making an infinite recursion and checking if it results in an infinite loop or a stack overflow (I did this with GCC and found out that `-O2` is sufficient), but I want to be able to check a certain function that I know will terminate anyway. I&#39;d love to have an easy way of checking this :)

----

After some testing, I discovered that destructors ruin the possibility of making this optimization. It can sometimes be worth it to change the scoping of certain variables and temporaries to make sure they go out of scope before the return-statement starts.

If any destructor needs to be run after the tail-call, the tail-call optimization can not be done.

Which, if any, C++ compilers do tail-recursion optimization?

I almost understand how tail recursion works and the difference between it and a normal recursion. I **only** don&#39;t understand why it **doesn&#39;t** require stack to remember its return address.


    // tail recursion
    int fac_times (int n, int acc) {
        if (n == 0) return acc;
        else return fac_times(n - 1, acc * n);
    }
         
    int factorial (int n) {
        return fac_times (n, 1);
    }
    
    // normal recursion
    int factorial (int n) {
        if (n == 0) return 1;
        else return n * factorial(n - 1);
    }

There is nothing to do after calling a function itself in a tail recursion function but it doesn&#39;t make sense for me.

How exactly does tail recursion work?

I found [this question][1] about which languages optimize tail recursion. Why C# doesn&#39;t optimize tail recursion, whenever possible?

For a concrete case, why isn&#39;t this method optimized into a loop ([Visual&amp;nbsp;Studio&amp;nbsp;2008][2] 32-bit, if that matters)?:

    private static void Foo(int i)
    {
        if (i == 1000000)
            return;

        if (i % 100 == 0)
            Console.WriteLine(i);

        Foo(i+1);
    }

  [1]: https://stackoverflow.com/questions/340762/which-languages-support-tail-recursion-optimization
  [2]: http://en.wikipedia.org/wiki/Microsoft_Visual_Studio#Visual_Studio_2008


Why doesn&#39;t .NET/C# optimize for tail-call recursion?

I saw this quote on the question: https://stackoverflow.com/questions/105710

&gt; Scala in particular doesn&#39;t support tail-call elimination except in self-recursive functions, which limits the kinds of composition you can do (this is a fundamental limitation of the JVM).

Is this true?  If so, what is it about the JVM that creates this fundamental limitation?

Does the JVM prevent tail call optimizations?

I discovered the &quot;time&quot; command in unix today and thought I&#39;d use it to check the difference in runtimes between tail-recursive and normal recursive functions in Haskell.

I wrote the following functions:

    --tail recursive
    fac :: (Integral a) =&gt; a -&gt; a
    fac x = fac&#39; x 1 where
    	fac&#39; 1 y = y
    	fac&#39; x y = fac&#39; (x-1) (x*y) 
    
    --normal recursive
    facSlow :: (Integral a) =&gt; a -&gt; a
    facSlow 1 = 1
    facSlow x = x * facSlow (x-1)

These are valid keeping in mind they were solely for use with this project, so I didn&#39;t bother to check for zeroes or negative numbers.

However, upon writing a main method for each, compiling them, and running them with the &quot;time&quot; command, both had similar runtimes with the *normal* recursive function edging out the tail recursive one. This is contrary to what I&#39;d heard with regards to tail-recursive optimization in lisp. What&#39;s the reason for this?


Does Haskell have tail-recursive optimization?

Functional languages lead to use of recursion to solve a lot of problems, and therefore many of them perform Tail Call Optimization (TCO). TCO causes calls to a function from another function (or itself, in which case this feature is also known as Tail Recursion Elimination, which is a subset of TCO), as the last step of that function, to not need a new stack frame, which decreases overhead and memory usage.

Ruby obviously has &quot;borrowed&quot; a number of concepts from functional languages (lambdas, functions like map and so forth, etc.), which makes me curious: Does Ruby perform tail call optimization?

Does Ruby perform Tail Call Optimization?

I have a tail recursive pathfinding algorithm that I&#39;ve implemented in JavaScript and would like to know if any (all?) browsers would possibly get stack overflow exceptions.






Are any JavaScript engines tail call (TCO) optimized?

I have been trying to understand `Tail call optimization` in context of JavaScript and have written the below recursive and tail-recursive methods for `factorial()`.

**Recursive:**

    function factorial (n) {
      if (n &lt; 2) {
        return 1;
      } else {
        return n * factorial(n-1);
      }
    }

**Tail-recursive:**

    function factorial (n) {
      function fact(n, acc) {
        if (n &lt; 2) {
          return acc;
        } else {
          return fact(n-1, n * acc);
        }
      }

      return fact(n, 1)
    }

But I am not sure if the `tail-recursive` version of the function will be optimised by JavaScript compiler as it is done in other languages like Scala etc. Can someone help me out on this one?

Are functions in JavaScript tail-call optimized?

Whilst starting to learn lisp, I&#39;ve come across the term *tail-recursive*. What does it mean exactly?

What is tail recursion?

I wanted to test foldl vs foldr. From what I&#39;ve seen you should use foldl over foldr when ever you can due to tail reccursion optimization.

This makes sense. However, after running this test I am confused:

foldr (takes 0.057s when using time command):

    a::a -&gt; [a] -&gt; [a]
    a x = ([x] ++ )
    
    main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

    
foldl (takes 0.089s when using time command):

    b::[b] -&gt; b -&gt; [b]
    b xs = ( ++ xs). (\y-&gt;[y])
    
    main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

It&#39;s clear that this example is trivial, but I am confused as to why foldr is beating foldl. Shouldn&#39;t this be a clear case where foldl wins?
    


foldl is tail recursive, so how come foldr runs faster than foldl?

I was trying to figure out hands-on how tail calls are handled by the C# compiler.

(Answer: [They&#39;re not.][1] But the *64bit JIT(s)* WILL do TCE (tail call elimination). [Restrictions apply][2].)

So I wrote a small test using a recursive call that prints how many times it gets called before the `StackOverflowException` kills the process.

    class Program
    {
        static void Main(string[] args)
        {
            Rec();
        }

        static int sz = 0;
        static Random r = new Random();
        static void Rec()
        {
            sz++;

            //uncomment for faster, more imprecise runs
            //if (sz % 100 == 0)
            {
                //some code to keep this method from being inlined
                var zz = r.Next();  
                Console.Write(&quot;{0} Random: {1}\r&quot;, sz, zz);
            }
            
            //uncommenting this stops TCE from happening
            //else
            //{
            //    Console.Write(&quot;{0}\r&quot;, sz);
            //}

            Rec();
        }

Right on cue, the program ends with SO Exception on any of:

- &#39;Optimize build&#39; OFF (either Debug or Release)
- Target: x86
- Target: AnyCPU + &quot;Prefer 32 bit&quot; (this is new in VS 2012 and the first time I saw it. [More here][3].) 
- Some seemingly innocuous branch in the code (see commented &#39;else&#39; branch).

Conversely, using &#39;Optimize build&#39; ON + (Target = x64 or AnyCPU with &#39;Prefer 32bit&#39; OFF (on a 64bit CPU)), TCE happens and the counter keeps spinning up forever (ok, it arguably spins *down* each time its value overflows).

**But I noticed a behaviour I can&#39;t explain** in the `StackOverflowException` case: it never (?) happens at *exactly* the same stack depth. Here are the outputs of a few 32-bit runs, Release build:

    51600 Random: 1778264579
    Process is terminated due to StackOverflowException.

    51599 Random: 1515673450
    Process is terminated due to StackOverflowException.

    51602 Random: 1567871768
    Process is terminated due to StackOverflowException.

    51535 Random: 2760045665
    Process is terminated due to StackOverflowException.

And Debug build:

    28641 Random: 4435795885
    Process is terminated due to StackOverflowException.

    28641 Random: 4873901326  //never say never
    Process is terminated due to StackOverflowException.

    28623 Random: 7255802746
    Process is terminated due to StackOverflowException.

    28669 Random: 1613806023
    Process is terminated due to StackOverflowException.

The stack size is constant ([defaults to 1 MB][4]). The stack frames&#39; sizes are constant. 

So then, what can account for the (sometimes non-trivial) variation of stack depth when the `StackOverflowException` hits? 


UPDATE
--
Hans Passant raises the issue of `Console.WriteLine` touching P/Invoke, interop and possibly non-deterministic locking. 

So I simplified the code to this: 

    class Program
    {
        static void Main(string[] args)
        {
            Rec();
        }
        static int sz = 0;
        static void Rec()
        {
            sz++;
            Rec();
        }
    }

I ran it in Release/32bit/Optimization ON without a debugger. When the program crashes, I attach the debugger and check the value of the counter. 

And it *still* isn&#39;t the same on several runs. (Or my test is flawed.)

UPDATE: Closure
---
As suggested by fejesjoco, I looked into ASLR (Address space layout randomization). 

It&#39;s a security technique that makes it hard for buffer overflow attacks to find the precise location of (e.g.) specific system calls, by randomizing various things in the process address space, including the stack position and, apparently, its size.

**The theory sounds good. Let&#39;s put it into practice!**

In order to test this, I used a Microsoft tool specific for the task: [EMET or The Enhanced Mitigation Experience Toolkit][5]. It allows setting the ASLR flag (and a lot more) on a system- or process-level.  
(There is also a [system-wide, registry hacking alternative][6] that I didn&#39;t try)

![EMET GUI][7]

In order to verify the effectiveness of the tool, I also discovered that [Process Explorer][8] duly reports the status of the ASLR flag in the &#39;Properties&#39; page of the process. Never saw that until today :)

![enter image description here][9]

Theoretically, EMET can (re)set the ASLR flag for a single process. In practice, it didn&#39;t seem to change anything (see above image).

However, I disabled ASLR for the entire system and (one reboot later) I could finally verify that indeed, the SO exception now always happens at the same stack depth.

BONUS
---
ASLR-related, in older news: [How Chrome got pwned][10]


  [1]: https://stackoverflow.com/questions/491376/why-doesnt-net-c-optimize-for-tail-call-recursion
  [2]: https://web.archive.org/web/20130321234831/http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx
  [3]: https://stackoverflow.com/questions/12066638/what-is-the-purpose-of-the-prefer-32-bit-setting-in-visual-studio-2012-and-how
  [4]: http://msdn.microsoft.com/en-us/library/windows/desktop/ms686774%28v=vs.85%29.aspx
  [5]: http://technet.microsoft.com/en-us/security/jj653751
  [6]: https://stackoverflow.com/questions/9560993/how-do-you-disable-aslr-address-space-layout-randomization-on-windows-7-x64
  [7]: http://i.stack.imgur.com/Uzf8i.png
  [8]: http://technet.microsoft.com/en-us/sysinternals/bb896653.aspx
  [9]: http://i.stack.imgur.com/LcsBf.png
  [10]: http://9to5google.com/2012/03/07/vupen-conquers-chrome-at-pwn2own-security-conference-google-must-pay-cash-reward-for-french-teams-hack/

Why does a recursive call cause StackOverflow at different stack depths?

I am getting introduced to Functional Programming [FP] (using Scala). One thing that is coming out from my initial learnings is that FPs rely heavily on recursion. And also it seems like, in *pure* FPs the only way to do iterative stuff is by writing recursive functions.

And because of the heavy usage of recursion seems the next thing that FPs had to worry about were `StackoverflowExceptions` typically due to long winding recursive calls. This was tackled by introducing some optimizations (tail recursion related optimizations in maintenance of stackframes and `@tailrec` annotation from Scala v2.8 onwards) 

Can someone please enlighten me why recursion is so important to functional programming paradigm? Is there something in the specifications of functional programming languages which gets &quot;violated&quot; if we do stuff iteratively? If yes, then I am keen to know that as well.

PS: Note that I am newbie to functional programming so feel free to point me to existing resources if they explain/answer my question. Also I do understand that Scala in particular provides support for doing iterative stuff as well.

Functional Programming - Lots of emphasis on recursion, why?

How do I tell if gcc (more specifically, g++) is optimizing tail recursion *in a particular function*?  (Because it&#39;s come up a few times: I don&#39;t want to test if gcc can optimize tail recursion in general.  I want to know if it optimizes **my** tail recursive function.)

If your answer is &quot;look at the generated assembler&quot;, I&#39;d like to know exactly what I&#39;m looking for, and whether or not I could write a simple program that examines the assembler to see if there&#39;s optimization.

PS.  I know this appears as part of the question [Which, if any, C++ compilers do tail-recursion optimization?][1] from 5 months ago.  However, I don&#39;t think *this part* of that question was answered satisfactorily.  (The answer there was &quot;The easiest way to check if the compiler did the optimization (that I know of) is perform a call that would otherwise result in a stack overflow – or looking at the assembly output.&quot;)

  [1]: https://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization


How do I check if gcc is performing tail-recursion optimization?

Can someone show me a simple tail-recursive function in C++?

Why is tail recursion better, if it even is?

What other kinds of recursion are there besides tail recursion?

Tail recursion in C++

Does Scala support tail recursion optimization?

I recently found a presentation about [F# for Python programmers][1], and after watching it, I decided to implement a solution to the &quot;ant puzzle&quot; on my own.

*There is an ant that can walk around on a planar grid. The ant can move one space at a time left, right, up or down.  That is, from the cell (x, y) the ant can go to cells (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the x and y coordinates are greater than 25 are inaccessible to the ant. For example, the point (59,79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. The question is: How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?*

I implemented my solution in 30 lines of [OCaml first][2], and tried it out:

    $ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
    $ time ./puzzle
    Points: 148848

    real    0m0.143s
    user    0m0.127s
    sys     0m0.013s

Neat, my result is the same as that of [leonardo&#39;s implementation, in D and C++][3]. Comparing to Leonardo&#39;s C++ implementation, the OCaml version runs approx 2 times slower than C++. Which is OK, given that Leonardo used a queue to remove recursion.

I then [translated the code to F#][4] ... and here&#39;s what I got:

    Thanassis@HOME /g/Tmp/ant.fsharp
    $ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
    Microsoft (R) F# 2.0 Compiler build 2.0.0.0
    Copyright (c) Microsoft Corporation. All Rights Reserved.
    
    Thanassis@HOME /g/Tmp/ant.fsharp
    $ ./ant.exe
    
    Process is terminated due to StackOverflowException.
    Quit
    
    Thanassis@HOME /g/Tmp/ant.fsharp
    $ /g/Program\ Files/Microsoft\ F#/v4.0/Fsc.exe ant.fs
    Microsoft (R) F# 2.0 Compiler build 4.0.30319.1
    Copyright (c) Microsoft Corporation. All Rights Reserved.
    
    Thanassis@HOME /g/Tmp/ant.fsharp
    $ ./ant.exe
    
    Process is terminated due to StackOverflowException

Stack overflow... with both versions of F# I have in my machine...
Out of curiosity, I then took the generated binary (ant.exe) and run it under Arch Linux/Mono:

    $ mono -V | head -1
    Mono JIT compiler version 2.10.5 (tarball Fri Sep  9 06:34:36 UTC 2011)
    
    $ time mono ./ant.exe
    Points: 148848
    
    real    1m24.298s
    user    0m0.567s
    sys     0m0.027s

Surprisingly, it runs under Mono 2.10.5 (i.e. no stack overflow) - but it takes 84 seconds, i.e. 587 times slower than OCaml - oops. 

So this program...

- runs fine under OCaml
- doesn&#39;t work at all under .NET/F#
- works, but is very slow, under Mono/F#.

Why?

**EDIT:** Weirdness continues - Using &quot;--optimize+ --checked-&quot; makes the problem disappear,  **but only under ArchLinux/Mono** ; under Windows XP and Windows 7/64bit, even the optimized version of the binary stack overflows.

**Final EDIT**: I found out the answer myself - see below.

  [1]: http://combiol.org/fs/FSUG_FS4PPv2.pptx
  [2]: http://pastebin.com/EzMt466b
  [3]: http://leonardo-m.livejournal.com/
  [4]: http://pastebin.com/0Vx5GTBQ



All Tail Recursion Solutions on Gang of Coders

Total of 21 Tail Recursion Solutions