<p>Whilst starting to learn lisp, I've come across the term <em>tail-recursive</em>. What does it mean exactly?</p>

[{'answer_id': 33924, 'author': 'Matt Hamilton', 'author_id': 615, 'author_profile': 'https://Stackoverflow.com/users/615', 'pm_score': 4, 'selected': False, 'text': '<p>I\'m not a Lisp programmer, but I think <a href="http://en.wikipedia.org/wiki/Tail_recursion" rel="noreferrer">this</a> will help.</p>\n\n<p>Basically it\'s a style of programming such that the recursive call is the last thing you do.</p>\n'}, {'answer_id': 33928, 'author': 'FlySwat', 'author_id': 1965, 'author_profile': 'https://Stackoverflow.com/users/1965', 'pm_score': 6, 'selected': False, 'text': '<p>Using regular recursion, each recursive call pushes another entry onto the call stack. When the recursion is completed, the app then has to pop each entry off all the way back down.</p>\n\n<p>With tail recursion, depending on language the compiler may be able to collapse the stack down to one entry, so you save stack space...A large recursive query can actually cause a stack overflow.</p>\n\n<p>Basically Tail recursions are able to be optimized into iteration.</p>\n'}, {'answer_id': 33929, 'author': 'Peter Meyer', 'author_id': 1875, 'author_profile': 'https://Stackoverflow.com/users/1875', 'pm_score': 6, 'selected': False, 'text': '<p>Tail recursion refers to the recursive call being last in the last logic instruction in the recursive algorithm.</p>\n\n<p>Typically in recursion, you have a <em>base-case</em> which is what stops the recursive calls and begins popping the call stack.  To use a classic example, though more C-ish than Lisp, the factorial function illustrates tail recursion.  The recursive call occurs <em>after</em> checking the base-case condition.</p>\n\n<pre class="lang-c++ prettyprint-override"><code>factorial(x, fac=1) {\n  if (x == 1)\n     return fac;\n   else\n     return factorial(x-1, x*fac);\n}\n</code></pre>\n\n<p>The initial call to factorial would be <code>factorial(n)</code> where <code>fac=1</code> (default value) and n is the number for which the factorial is to be calculated.</p>\n'}, {'answer_id': 33930, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 10, 'selected': False, 'text': "<p>In <strong>traditional recursion</strong>, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.</p>\n\n<p>In <strong>tail recursion</strong>, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of <code>(return (recursive-function params))</code>. <strong>Basically, the return value of any given recursive step is the same as the return value of the next recursive call</strong>.</p>\n\n<p>The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow <em>snicker</em> with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.</p>\n"}, {'answer_id': 33931, 'author': 'Kyle Cronin', 'author_id': 658, 'author_profile': 'https://Stackoverflow.com/users/658', 'pm_score': 6, 'selected': False, 'text': '<p>Instead of explaining it with words, here\'s an example. This is a Scheme version of the factorial function:\n</p>\n\n<pre class="lang-scm prettyprint-override"><code>(define (factorial x)\n  (if (= x 0) 1\n      (* x (factorial (- x 1)))))\n</code></pre>\n\n<p>Here is a version of factorial that is tail-recursive:</p>\n\n<pre class="lang-scm prettyprint-override"><code>(define factorial\n  (letrec ((fact (lambda (x accum)\n                   (if (= x 0) accum\n                       (fact (- x 1) (* accum x))))))\n    (lambda (x)\n      (fact x 1))))\n</code></pre>\n\n<p>You will notice in the first version that the recursive call to fact is fed into the multiplication expression, and therefore the state has to be saved on the stack when making the recursive call. In the tail-recursive version there is no other S-expression waiting for the value of the recursive call, and since there is no further work to do, the state doesn\'t have to be saved on the stack. As a rule, Scheme tail-recursive functions use constant stack space.</p>\n'}, {'answer_id': 34105, 'author': 'Pat', 'author_id': 238, 'author_profile': 'https://Stackoverflow.com/users/238', 'pm_score': 6, 'selected': False, 'text': "<p>The jargon file has this to say about the definition of tail recursion:</p>\n\n<p><strong>tail recursion</strong> /n./</p>\n\n<p>If you aren't sick of it already, see tail recursion. </p>\n"}, {'answer_id': 34540, 'author': 'Hoffmann', 'author_id': 3485, 'author_profile': 'https://Stackoverflow.com/users/3485', 'pm_score': 7, 'selected': False, 'text': '<p>This excerpt from the book <em>Programming in Lua</em> shows <a href="http://www.lua.org/pil/6.3.html" rel="noreferrer">how to make a proper tail recursion</a> (in Lua, but should apply to Lisp too) and why it\'s better.</p>\n\n<blockquote>\n  <p>A <em>tail call</em> [tail recursion] is a kind of goto dressed\n  as a call. A tail call happens when a\n  function calls another as its last\n  action, so it has nothing else to do.\n  For instance, in the following code,\n  the call to <code>g</code> is a tail call:</p>\n  \n  <pre class="lang-lua prettyprint-override"><code>function f (x)\n  return g(x)\nend\n</code></pre>\n  \n  <p>After <code>f</code> calls <code>g</code>, it has nothing else\n  to do. In such situations, the program\n  does not need to return to the calling\n  function when the called function\n  ends. Therefore, after the tail call,\n  the program does not need to keep any\n  information about the calling function\n  in the stack. ...</p>\n  \n  <p>Because a proper tail call uses no\n  stack space, there is no limit on the\n  number of "nested" tail calls that a\n  program can make. For instance, we can\n  call the following function with any\n  number as argument; it will never\n  overflow the stack:</p>\n  \n  <pre class="lang-lua prettyprint-override"><code>function foo (n)\n  if n &gt; 0 then return foo(n - 1) end\nend\n</code></pre>\n  \n  <p>... As I said earlier, a tail call is a\n  kind of goto. As such, a quite useful\n  application of proper tail calls in\n  Lua is for programming state machines.\n  Such applications can represent each\n  state by a function; to change state\n  is to go to (or to call) a specific\n  function. As an example, let us\n  consider a simple maze game. The maze\n  has several rooms, each with up to\n  four doors: north, south, east, and\n  west. At each step, the user enters a\n  movement direction. If there is a door\n  in that direction, the user goes to\n  the corresponding room; otherwise, the\n  program prints a warning. The goal is\n  to go from an initial room to a final\n  room.</p>\n  \n  <p>This game is a typical state machine,\n  where the current room is the state.\n  We can implement such maze with one\n  function for each room. We use tail\n  calls to move from one room to\n  another. A small maze with four rooms\n  could look like this:</p>\n  \n  <pre class="lang-lua prettyprint-override"><code>function room1 ()\n  local move = io.read()\n  if move == "south" then return room3()\n  elseif move == "east" then return room2()\n  else print("invalid move")\n       return room1()   -- stay in the same room\n  end\nend\n\nfunction room2 ()\n  local move = io.read()\n  if move == "south" then return room4()\n  elseif move == "west" then return room1()\n  else print("invalid move")\n       return room2()\n  end\nend\n\nfunction room3 ()\n  local move = io.read()\n  if move == "north" then return room1()\n  elseif move == "east" then return room4()\n  else print("invalid move")\n       return room3()\n  end\nend\n\nfunction room4 ()\n  print("congratulations!")\nend\n</code></pre>\n</blockquote>\n\n<p>So you see, when you make a recursive call like:</p>\n\n<pre class="lang-lua prettyprint-override"><code>function x(n)\n  if n==0 then return 0\n  n= n-2\n  return x(n) + 1\nend\n</code></pre>\n\n<p>This is not tail recursive because you still have things to do (add 1) in that function after the recursive call is made. If you input a very high number it will probably cause a stack overflow.</p>\n'}, {'answer_id': 36985, 'author': 'Chris Conway', 'author_id': 1412, 'author_profile': 'https://Stackoverflow.com/users/1412', 'pm_score': 8, 'selected': False, 'text': '<p>An important point is that tail recursion is essentially equivalent to looping. It\'s not just a matter of compiler optimization, but a fundamental fact about expressiveness. This goes both ways: you can take any loop of the form</p>\n\n<pre class="lang-c prettyprint-override"><code>while(E) { S }; return Q\n</code></pre>\n\n<p>where <code>E</code> and <code>Q</code> are expressions and <code>S</code> is a sequence of statements, and turn it into a tail recursive function</p>\n\n<pre class="lang-c prettyprint-override"><code>f() = if E then { S; return f() } else { return Q }\n</code></pre>\n\n<p>Of course, <code>E</code>, <code>S</code>, and <code>Q</code> have to be defined to compute some interesting value over some variables. For example, the looping function</p>\n\n<pre class="lang-c prettyprint-override"><code>sum(n) {\n  int i = 1, k = 0;\n  while( i &lt;= n ) {\n    k += i;\n    ++i;\n  }\n  return k;\n}\n</code></pre>\n\n<p>is equivalent to the tail-recursive function(s)</p>\n\n<pre class="lang-c prettyprint-override"><code>sum_aux(n,i,k) {\n  if( i &lt;= n ) {\n    return sum_aux(n,i+1,k+i);\n  } else {\n    return k;\n  }\n}\n\nsum(n) {\n  return sum_aux(n,1,0);\n}\n</code></pre>\n\n<p>(This "wrapping" of the tail-recursive function with a function with fewer parameters is a common functional idiom.)</p>\n'}, {'answer_id': 37010, 'author': 'Lorin Hochstein', 'author_id': 742, 'author_profile': 'https://Stackoverflow.com/users/742', 'pm_score': 12, 'selected': True, 'text': '<p>Consider a simple function that adds the first N natural numbers. (e.g. <code>sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15</code>).</p>\n<p>Here is a simple JavaScript implementation that uses recursion:</p>\n<pre class="lang-js prettyprint-override"><code>function recsum(x) {\n    if (x === 0) {\n        return 0;\n    } else {\n        return x + recsum(x - 1);\n    }\n}\n</code></pre>\n<p>If you called <code>recsum(5)</code>, this is what the JavaScript interpreter would evaluate:</p>\n<pre class="lang-js prettyprint-override"><code>recsum(5)\n5 + recsum(4)\n5 + (4 + recsum(3))\n5 + (4 + (3 + recsum(2)))\n5 + (4 + (3 + (2 + recsum(1))))\n5 + (4 + (3 + (2 + (1 + recsum(0)))))\n5 + (4 + (3 + (2 + (1 + 0))))\n5 + (4 + (3 + (2 + 1)))\n5 + (4 + (3 + 3))\n5 + (4 + 6)\n5 + 10\n15\n</code></pre>\n<p>Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.</p>\n<p>Here\'s a tail-recursive version of the same function:</p>\n<pre class="lang-js prettyprint-override"><code>function tailrecsum(x, running_total = 0) {\n    if (x === 0) {\n        return running_total;\n    } else {\n        return tailrecsum(x - 1, running_total + x);\n    }\n}\n</code></pre>\n<p>Here\'s the sequence of events that would occur if you called <code>tailrecsum(5)</code>, (which would effectively be <code>tailrecsum(5, 0)</code>, because of the default second argument).</p>\n<pre class="lang-js prettyprint-override"><code>tailrecsum(5, 0)\ntailrecsum(4, 5)\ntailrecsum(3, 9)\ntailrecsum(2, 12)\ntailrecsum(1, 14)\ntailrecsum(0, 15)\n15\n</code></pre>\n<p>In the tail-recursive case, with each evaluation of the recursive call, the <code>running_total</code> is updated.</p>\n<p><em>Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don\'t support <a href="https://stackoverflow.com/questions/310974/what-is-tail-call-optimization">tail call optimization</a>. However, while tail call optimization is <a href="https://www.ecma-international.org/ecma-262/6.0/#sec-tail-position-calls" rel="noreferrer">part of the ECMAScript 2015 spec</a>, most JavaScript interpreters <a href="https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation)" rel="noreferrer">don\'t support it</a>.</em></p>\n'}, {'answer_id': 37273, 'author': 'Chris Smith', 'author_id': 322, 'author_profile': 'https://Stackoverflow.com/users/322', 'pm_score': 5, 'selected': False, 'text': '<p>It means that rather than needing to push the instruction pointer on the stack, you can simply jump to the top of a recursive function and continue execution. This allows for functions to recurse indefinitely without overflowing the stack. </p>\n\n<p>I wrote a <a href="http://blogs.msdn.com/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx" rel="noreferrer">blog</a> post on the subject, which has graphical examples of what the stack frames look like.</p>\n'}, {'answer_id': 39604, 'author': 'magice', 'author_id': 227049, 'author_profile': 'https://Stackoverflow.com/users/227049', 'pm_score': 3, 'selected': False, 'text': '<p>Recursion means a function calling itself. For example:</p>\n\n<pre class="lang-lisp prettyprint-override"><code>(define (un-ended name)\n  (un-ended \'me)\n  (print "How can I get here?"))\n</code></pre>\n\n<p>Tail-Recursion means the recursion that conclude the function:</p>\n\n<pre class="lang-lisp prettyprint-override"><code>(define (un-ended name)\n  (print "hello")\n  (un-ended \'me))\n</code></pre>\n\n<p>See, the last thing un-ended function (procedure, in Scheme jargon) does is to call itself. Another (more useful) example is:</p>\n\n<pre class="lang-lisp prettyprint-override"><code>(define (map lst op)\n  (define (helper done left)\n    (if (nil? left)\n        done\n        (helper (cons (op (car left))\n                      done)\n                (cdr left))))\n  (reverse (helper \'() lst)))\n</code></pre>\n\n<p>In the helper procedure, the LAST thing it does if the left is not nil is to call itself (AFTER cons something and cdr something). This is basically how you map a list.</p>\n\n<p>The tail-recursion has a great advantage that the interpreter (or compiler, dependent on the language and vendor) can optimize it, and transform it into something equivalent to a while loop. As matter of fact, in Scheme tradition, most "for" and "while" loop is done in a tail-recursion manner (there is no for and while, as far as I know).</p>\n'}, {'answer_id': 159975, 'author': 'Brad Gilbert', 'author_id': 1337, 'author_profile': 'https://Stackoverflow.com/users/1337', 'pm_score': 3, 'selected': False, 'text': '<p>here is a Perl 5 version of the <code>tailrecsum</code> function mentioned earlier.</p>\n\n<pre class="lang-perl prettyprint-override"><code>sub tail_rec_sum($;$){\n  my( $x,$running_total ) = (@_,0);\n\n  return $running_total unless $x;\n\n  @_ = ($x-1,$running_total+$x);\n  goto &amp;tail_rec_sum; # throw away current stack frame\n}\n</code></pre>\n'}, {'answer_id': 202904, 'author': 'jorgetown', 'author_id': 7465, 'author_profile': 'https://Stackoverflow.com/users/7465', 'pm_score': 4, 'selected': False, 'text': '<p>In Java, here\'s a possible tail recursive implementation of the Fibonacci function:</p>\n\n<pre class="lang-java prettyprint-override"><code>public int tailRecursive(final int n) {\n    if (n &lt;= 2)\n        return 1;\n    return tailRecursiveAux(n, 1, 1);\n}\n\nprivate int tailRecursiveAux(int n, int iter, int acc) {\n    if (iter == n)\n        return acc;\n    return tailRecursiveAux(n, ++iter, acc + iter);\n}\n</code></pre>\n\n<p>Contrast this with the standard recursive implementation:</p>\n\n<pre class="lang-java prettyprint-override"><code>public int recursive(final int n) {\n    if (n &lt;= 2)\n        return 1;\n    return recursive(n - 1) + recursive(n - 2);\n}\n</code></pre>\n'}, {'answer_id': 4483714, 'author': 'AbuZubair', 'author_id': 547780, 'author_profile': 'https://Stackoverflow.com/users/547780', 'pm_score': 5, 'selected': False, 'text': '<p>Here is a quick code snippet comparing two functions. The first is traditional recursion for finding the factorial of a given number. The second uses tail recursion. </p>\n\n<p>Very simple and intuitive to understand.</p>\n\n<p>An easy way to tell if a recursive function is a tail recursive is if it returns a concrete value in the base case. Meaning that it doesn\'t return 1 or true or anything like that. It will more than likely return some variant of one of the method parameters.</p>\n\n<p>Another way is to tell is if the recursive call is free of any addition, arithmetic, modification, etc... Meaning its nothing but a pure recursive call. </p>\n\n<pre class="lang-c prettyprint-override"><code>public static int factorial(int mynumber) {\n    if (mynumber == 1) {\n        return 1;\n    } else {            \n        return mynumber * factorial(--mynumber);\n    }\n}\n\npublic static int tail_factorial(int mynumber, int sofar) {\n    if (mynumber == 1) {\n        return sofar;\n    } else {\n        return tail_factorial(--mynumber, sofar * mynumber);\n    }\n}\n</code></pre>\n'}, {'answer_id': 9652860, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 3, 'selected': False, 'text': '<p>Here is a Common Lisp example that does factorials using tail-recursion.  Due to the stack-less nature, one could perform insanely large factorial computations ... </p>\n\n<pre class="lang-lisp prettyprint-override"><code>(defun ! (n &amp;optional (product 1))\n    (if (zerop n) product\n        (! (1- n) (* product n))))\n</code></pre>\n\n<p>And then for fun you could try <code>(format nil "~R" (! 25))</code></p>\n'}, {'answer_id': 23349362, 'author': 'devinbost', 'author_id': 1887281, 'author_profile': 'https://Stackoverflow.com/users/1887281', 'pm_score': 3, 'selected': False, 'text': '<p>To understand some of the core differences between tail-call recursion and non-tail-call recursion we can explore the .NET implementations of these techniques. </p>\n\n<p>Here is an article with some examples in C#, F#, and C++\\CLI: <a href="http://blogs.msdn.com/b/jomo_fisher/archive/2007/09/19/adventures-in-f-tail-recursion-in-three-languages.aspx" rel="nofollow noreferrer">Adventures in Tail Recursion in C#, F#, and C++\\CLI</a>.</p>\n\n<p>C# does not optimize for tail-call recursion whereas F# does.</p>\n\n<p>The differences of principle involve loops vs. Lambda calculus. C# is designed with loops in mind whereas F# is built from the principles of Lambda calculus. For a very good (and free) book on the principles of Lambda calculus, see <a href="http://mitpress.mit.edu/sicp/" rel="nofollow noreferrer">Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman</a>. </p>\n\n<p>Regarding tail calls in F#, for a very good introductory article, see <a href="http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx" rel="nofollow noreferrer">Detailed Introduction to Tail Calls in F#</a>. Finally, here is an article that covers the difference between non-tail recursion and tail-call recursion (in F#): <a href="https://stackoverflow.com/questions/3248091/f-tail-recursive-function-example">Tail-recursion vs. non-tail recursion in F sharp</a>.</p>\n\n<p>If you want to read about some of the design differences of tail-call recursion between C# and F#, see <a href="https://stackoverflow.com/questions/15864670/generate-tail-call-opcode">Generating Tail-Call Opcode in C# and F#</a>.</p>\n\n<p>If you care enough to want to know what conditions prevent the C# compiler from performing tail-call optimizations, see this article: <a href="http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx" rel="nofollow noreferrer">JIT CLR tail-call conditions</a>.</p>\n'}, {'answer_id': 34394967, 'author': 'Abhiroop Sarkar', 'author_id': 1942289, 'author_profile': 'https://Stackoverflow.com/users/1942289', 'pm_score': 5, 'selected': False, 'text': '<p>The best way for me to understand <code>tail call recursion</code> is a special case of recursion where the <strong>last call</strong>(or the tail call) is the function itself.</p>\n\n<p>Comparing the examples provided in Python:</p>\n\n<pre><code>def recsum(x):\n if x == 1:\n  return x\n else:\n  return x + recsum(x - 1)\n</code></pre>\n\n<p>^RECURSION</p>\n\n<pre><code>def tailrecsum(x, running_total=0):\n  if x == 0:\n    return running_total\n  else:\n    return tailrecsum(x - 1, running_total + x)\n</code></pre>\n\n<p>^TAIL RECURSION</p>\n\n<p>As you can see in the general recursive version, the final call in the code block is <code>x + recsum(x - 1)</code>. So after calling the <code>recsum</code> method, there is another operation which is <code>x + ..</code>.</p>\n\n<p>However, in the tail recursive version, the final call(or the tail call) in the code block is <code>tailrecsum(x - 1, running_total + x)</code> which means the last call is made to the method itself and no operation after that.</p>\n\n<p>This point is important because tail recursion as seen here is not making the memory grow because when the underlying VM sees a function calling itself in a tail position (the last expression to be evaluated in a function), it eliminates the current stack frame, which is known as Tail Call Optimization(TCO).</p>\n\n<h2>EDIT</h2>\n\n<p><em>NB. Do bear in mind that the example above is written in Python whose runtime does not support TCO. This is just an example to explain the point. TCO is supported in languages like Scheme, Haskell etc</em></p>\n'}, {'answer_id': 38050598, 'author': 'ayushgp', 'author_id': 3719089, 'author_profile': 'https://Stackoverflow.com/users/3719089', 'pm_score': 3, 'selected': False, 'text': '<p>This is an excerpt from <a href="https://xuanji.appspot.com/isicp/1-2-procedures.html" rel="noreferrer">Structure and Interpretation of Computer Programs</a> about tail recursion.</p>\n\n<blockquote>\n  <p>In contrasting iteration and recursion, we must be careful not to\n  confuse the notion of a recursive process with the notion of a\n  recursive procedure. When we describe a procedure as recursive, we are\n  referring to the syntactic fact that the procedure definition refers\n  (either directly or indirectly) to the procedure itself. But when we\n  describe a process as following a pattern that is, say, linearly\n  recursive, we are speaking about how the process evolves, not about\n  the syntax of how a procedure is written. It may seem disturbing that\n  we refer to a recursive procedure such as fact-iter as generating an\n  iterative process. However, the process really is iterative: Its state\n  is captured completely by its three state variables, and an\n  interpreter need keep track of only three variables in order to\n  execute the process.</p>\n  \n  <p>One reason that the distinction between process and procedure may be\n  confusing is that most implementations of common languages (including Ada, Pascal, and\n  C) are designed in such a way that the interpretation of any recursive\n  procedure consumes an amount of memory that grows with the number of\n  procedure calls, even when the process described is, in principle,\n  iterative. As a consequence, these languages can describe iterative\n  processes only by resorting to special-purpose “looping constructs”\n  such as do, repeat, until, for, and while. <strong>The implementation of\n  Scheme does not share this defect. It\n  will execute an iterative process in constant space, even if the\n  iterative process is described by a recursive procedure. An\n  implementation with this property is called tail-recursive.</strong> With a\n  tail-recursive implementation, iteration can be expressed using the\n  ordinary procedure call mechanism, so that special iteration\n  constructs are useful only as syntactic sugar.</p>\n</blockquote>\n'}, {'answer_id': 40498100, 'author': 'justyy', 'author_id': 1479619, 'author_profile': 'https://Stackoverflow.com/users/1479619', 'pm_score': 3, 'selected': False, 'text': '<p>In short, a tail recursion has the recursive call as the <strong>last</strong> statement in the function so that it doesn\'t have to wait for the recursive call.</p>\n\n<p>So this is a tail recursion i.e. N(x - 1, p * x) is the last statement in the function where the compiler is clever to figure out that it can be optimised to a for-loop (factorial). The second parameter p carries the intermediate product value. </p>\n\n<pre><code>function N(x, p) {\n   return x == 1 ? p : N(x - 1, p * x);\n}\n</code></pre>\n\n<p>This is the non-tail-recursive way of writing the above factorial function (although some C++ compilers may be able to optimise it anyway).</p>\n\n<pre><code>function N(x) {\n   return x == 1 ? 1 : x * N(x - 1);\n}\n</code></pre>\n\n<p>but this is not:</p>\n\n<pre><code>function F(x) {\n  if (x == 1) return 0;\n  if (x == 2) return 1;\n  return F(x - 1) + F(x - 2);\n}\n</code></pre>\n\n<p>I did write a long post titled "<a href="https://helloacm.com/understanding-tail-recursion-visual-studio-c-assembly-view/" rel="noreferrer">Understanding Tail Recursion – Visual Studio C++ – Assembly View</a>"</p>\n\n<p><a href="https://i.stack.imgur.com/52QrO.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/52QrO.jpg" alt="enter image description here"></a></p>\n'}, {'answer_id': 41305954, 'author': 'Mulan', 'author_id': 633183, 'author_profile': 'https://Stackoverflow.com/users/633183', 'pm_score': 3, 'selected': False, 'text': '<p>Tail recursion is the life you are living right now. You constantly recycle the same stack frame, over and over, because there\'s no reason or means to return to a "previous" frame. The past is over and done with so it can be discarded. You get one frame, forever moving into the future, until your process inevitably dies.</p>\n\n<p><sub>The analogy breaks down when you consider some processes might utilize additional frames but are still considered tail-recursive if the stack does not grow infinitely.</sub></p>\n'}, {'answer_id': 44924202, 'author': 'pnkfelix', 'author_id': 36585, 'author_profile': 'https://Stackoverflow.com/users/36585', 'pm_score': 2, 'selected': False, 'text': '<p>This question has a lot of great answers... but I cannot help but chime in with an alternative take on how to define "tail recursion", or at least "proper tail recursion." Namely: should one look at it as a property of a particular expression in a program? Or should one look at it as a property of an <em>implementation of a programming language</em>?</p>\n\n<p>For more on the latter view, there is a classic <a href="http://www.cesura17.net/~will/professional/research/papers/tail.pdf" rel="nofollow noreferrer" title="Proper Tail Recursion and Space Efficiency (PLDI 1998)">paper</a> by Will Clinger, "Proper Tail Recursion and Space Efficiency" (PLDI 1998), that defined "proper tail recursion" as a property of a programming language implementation. The definition is constructed to allow one to ignore implementation details (such as whether the call stack is actually represented via the runtime stack or via a heap-allocated linked list of frames).</p>\n\n<p>To accomplish this, it uses asymptotic analysis: not of program execution time as one usually sees, but rather of program <em>space usage</em>. This way, the space usage of a heap-allocated linked list vs a runtime call stack ends up being asymptotically equivalent; so one gets to ignore that programming language implementation detail (a detail which certainly matters quite a bit in practice, but can muddy the waters quite a bit when one attempts to determine whether a given implementation is satisfying the requirement to be "property tail recursive")</p>\n\n<p>The paper is worth careful study for a number of reasons:</p>\n\n<ul>\n<li><p>It gives an inductive definition of the <em>tail expressions</em> and <em>tail calls</em> of a program. (Such a definition, and why such calls are important, seems to be the subject of most of the other answers given here.)</p>\n\n<p>Here are those definitions, just to provide a flavor of the text:</p>\n\n<blockquote>\n  <p><strong>Definition 1</strong> The <em>tail expressions</em> of a program written in Core Scheme are defined inductively as follows.</p>\n  \n  <ol>\n  <li>The body of a lambda expression is a tail expression</li>\n  <li>If <code>(if E0 E1 E2)</code> is a tail expression, then both <code>E1</code> and <code>E2</code> are tail expressions.</li>\n  <li>Nothing else is a tail expression.</li>\n  </ol>\n  \n  <p><strong>Definition 2</strong> A <em>tail call</em> is a tail expression that is a procedure call.</p>\n</blockquote></li>\n</ul>\n\n<p>(a tail recursive call, or as the paper says, "self-tail call" is a special case of a tail call where the procedure is invoked itself.)</p>\n\n<ul>\n<li><p>It provides formal definitions for six different "machines" for evaluating Core Scheme, where each machine has the same observable behavior <em>except</em> for the <em>asymptotic</em> space complexity class that each is in.</p>\n\n<p>For example, after giving definitions for machines with respectively, 1. stack-based memory management, 2. garbage collection but no tail calls, 3. garbage collection and tail calls, the paper continues onward with even more advanced storage management strategies, such as 4. "evlis tail recursion", where the environment does not need to be preserved across the evaluation of the last sub-expression argument in a tail call, 5. reducing the environment of a closure to <em>just</em> the free variables of that closure, and 6. so-called "safe-for-space" semantics as defined by <a href="http://www.cs.princeton.edu/~appel/papers/stack2.pdf" rel="nofollow noreferrer" title="Empirical and Analytic Study of Stack versus Heap Cost for Languages with Closures. (JFP 1996)">Appel and Shao</a>.</p></li>\n<li><p>In order to prove that the machines actually belong to six distinct space complexity classes, the paper, for each pair of machines under comparison, provides concrete examples of programs that will expose asymptotic space blowup on one machine but not the other.</p></li>\n</ul>\n\n<hr>\n\n<p>(Reading over my answer now, I\'m not sure if I\'m managed to actually capture the crucial points of the <a href="http://www.cesura17.net/~will/professional/research/papers/tail.pdf" rel="nofollow noreferrer" title="Proper Tail Recursion and Space Efficiency (PLDI 1998)">Clinger paper</a>. But, alas, I cannot devote more time to developing this answer right now.)</p>\n'}, {'answer_id': 47952480, 'author': 'coding_ninza', 'author_id': 8295641, 'author_profile': 'https://Stackoverflow.com/users/8295641', 'pm_score': 3, 'selected': False, 'text': '<blockquote>\n  <p>A tail recursion is a recursive function where the function calls\n  itself at the end ("tail") of the function in which no computation is\n  done after the return of recursive call. Many compilers optimize to\n  change a recursive call to a tail recursive or an iterative call.</p>\n</blockquote>\n\n<p>Consider the problem of computing factorial of a number.</p>\n\n<p>A straightforward approach would be:</p>\n\n<pre><code>  factorial(n):\n\n    if n==0 then 1\n\n    else n*factorial(n-1)\n</code></pre>\n\n<p>Suppose you call factorial(4). The recursion tree would be:</p>\n\n<pre><code>       factorial(4)\n       /        \\\n      4      factorial(3)\n     /             \\\n    3          factorial(2)\n   /                  \\\n  2                factorial(1)\n /                       \\\n1                       factorial(0)\n                            \\\n                             1    \n</code></pre>\n\n<p>The maximum recursion depth in the above case is O(n).</p>\n\n<p>However, consider the following example:</p>\n\n<pre><code>factAux(m,n):\nif n==0  then m;\nelse     factAux(m*n,n-1);\n\nfactTail(n):\n   return factAux(1,n);\n</code></pre>\n\n<p>Recursion tree for factTail(4) would be:</p>\n\n<pre><code>factTail(4)\n   |\nfactAux(1,4)\n   |\nfactAux(4,3)\n   |\nfactAux(12,2)\n   |\nfactAux(24,1)\n   |\nfactAux(24,0)\n   |\n  24\n</code></pre>\n\n<p>Here also, maximum recursion depth is O(n) but none of the calls adds any extra variable to the stack. Hence the compiler can do away with a stack.</p>\n'}, {'answer_id': 50231106, 'author': 'Abdullah Khan', 'author_id': 3094731, 'author_profile': 'https://Stackoverflow.com/users/3094731', 'pm_score': 2, 'selected': False, 'text': '<p>There are two basic kinds of recursions: <strong>head recursion</strong> and <strong>tail recursion.</strong>  </p>\n\n<blockquote>\n  <p>In <strong>head recursion</strong>, a function makes its recursive call and then\n  performs some more calculations, maybe using the result of the\n  recursive call, for example.</p>\n  \n  <p>In a <strong>tail recursive</strong> function, all calculations happen first and\n  the recursive call is the last thing that happens.</p>\n</blockquote>\n\n<p>Taken from <a href="https://oldfashionedsoftware.com/2008/09/27/tail-recursion-basics-in-scala/" rel="nofollow noreferrer">this</a> super awesome post. \nPlease consider reading it.</p>\n'}, {'answer_id': 54036034, 'author': 'V. S.', 'author_id': 10014202, 'author_profile': 'https://Stackoverflow.com/users/10014202', 'pm_score': 2, 'selected': False, 'text': '<p>Many people have already explained recursion here. I would like to cite a couple of thoughts about some advantages that recursion gives from the book “Concurrency in .NET, Modern patterns of concurrent and parallel programming” by Riccardo Terrell:  </p>\n\n<blockquote>\n  <p>“Functional recursion is the natural way to iterate in FP because it\n  avoids mutation of state. During each iteration, a new value is passed\n  into the loop constructor instead to be updated (mutated). In\n  addition, a recursive function can be composed, making your program\n  more modular, as well as introducing opportunities to exploit\n  parallelization."</p>\n</blockquote>\n\n<p>Here also are some interesting notes from the same book about tail recursion:</p>\n\n<blockquote>\n  <p>Tail-call recursion is a technique that converts a regular recursive\n  function into an optimized version that can handle large inputs\n  without any risks and side effects.  </p>\n  \n  <p>NOTE The primary reason for a tail call as an optimization is to\n  improve data locality, memory usage, and cache usage. By doing a tail\n  call, the callee uses the same stack space as the caller. This reduces\n  memory pressure. It marginally improves the cache because the same\n  memory is reused for subsequent callers and can stay in the cache,\n  rather than evicting an older cache line to make room for a new cache\n  line.</p>\n</blockquote>\n'}, {'answer_id': 54573509, 'author': 'Nursnaaz', 'author_id': 6949469, 'author_profile': 'https://Stackoverflow.com/users/6949469', 'pm_score': 4, 'selected': False, 'text': '<p>The recursive function is a function which <strong>calls by itself</strong></p>\n\n<p>It allows programmers to write efficient programs using a <strong>minimal amount of code</strong>.</p>\n\n<p>The downside is that they can <strong>cause infinite loops</strong> and other unexpected results if <strong>not written properly</strong>.</p>\n\n<p>I will explain both <strong>Simple Recursive function and Tail Recursive function</strong></p>\n\n<p>In order to write a <strong>Simple recursive function</strong> </p>\n\n<ol>\n<li><strong>The first point to consider is when should you decide on coming out \nof the loop which is the if loop</strong></li>\n<li><strong>The second is what process to do if we are our own function</strong></li>\n</ol>\n\n<p>From the given example:</p>\n\n<pre><code>public static int fact(int n){\n  if(n &lt;=1)\n     return 1;\n  else \n     return n * fact(n-1);\n}\n</code></pre>\n\n<p>From the above example</p>\n\n<pre><code>if(n &lt;=1)\n     return 1;\n</code></pre>\n\n<p>Is the deciding factor when to exit the loop</p>\n\n<pre><code>else \n     return n * fact(n-1);\n</code></pre>\n\n<p>Is the actual processing to be done </p>\n\n<p>Let me the break the task one by one for easy understanding.</p>\n\n<p>Let us see what happens internally if I run <code>fact(4)</code></p>\n\n<ol>\n<li><strong>Substituting n=4</strong></li>\n</ol>\n\n<pre><code>public static int fact(4){\n  if(4 &lt;=1)\n     return 1;\n  else \n     return 4 * fact(4-1);\n}\n</code></pre>\n\n<p><code>If</code> loop fails so it goes to <code>else</code> loop\nso it returns <code>4 * fact(3)</code></p>\n\n<ol start="2">\n<li><p>In stack memory, we have <code>4 * fact(3)</code></p>\n\n<p><strong>Substituting n=3</strong></p></li>\n</ol>\n\n<pre><code>public static int fact(3){\n  if(3 &lt;=1)\n     return 1;\n  else \n     return 3 * fact(3-1);\n}\n</code></pre>\n\n<p><code>If</code> loop fails so it goes to <code>else</code> loop</p>\n\n<p>so it returns <code>3 * fact(2)</code></p>\n\n<p>Remember we called ```4 * fact(3)``</p>\n\n<p>The output for <code>fact(3) = 3 * fact(2)</code></p>\n\n<p>So far the stack has <code>4 * fact(3) = 4 * 3 * fact(2)</code></p>\n\n<ol start="3">\n<li><p>In stack memory, we have <code>4 * 3 * fact(2)</code></p>\n\n<p><strong>Substituting n=2</strong></p></li>\n</ol>\n\n<pre><code>public static int fact(2){\n  if(2 &lt;=1)\n     return 1;\n  else \n     return 2 * fact(2-1);\n}\n</code></pre>\n\n<p><code>If</code> loop fails so it goes to <code>else</code> loop</p>\n\n<p>so it returns <code>2 * fact(1)</code></p>\n\n<p>Remember we called <code>4 * 3 * fact(2)</code></p>\n\n<p>The output for <code>fact(2) = 2 * fact(1)</code></p>\n\n<p>So far the stack has <code>4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)</code></p>\n\n<ol start="3">\n<li><p>In stack memory, we have <code>4 * 3 * 2 * fact(1)</code></p>\n\n<p><strong>Substituting n=1</strong></p></li>\n</ol>\n\n<pre><code>public static int fact(1){\n  if(1 &lt;=1)\n     return 1;\n  else \n     return 1 * fact(1-1);\n}\n</code></pre>\n\n<p><code>If</code> loop is true</p>\n\n<p>so it returns <code>1</code></p>\n\n<p>Remember we called <code>4 * 3 * 2 * fact(1)</code></p>\n\n<p>The output for <code>fact(1) = 1</code></p>\n\n<p>So far the stack has <code>4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1</code></p>\n\n<p>Finally, the result of <strong>fact(4) = 4 * 3 * 2 * 1 = 24</strong></p>\n\n<p><a href="https://i.stack.imgur.com/ELSwN.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/ELSwN.jpg" alt="enter image description here"></a></p>\n\n<p>The <strong>Tail Recursion</strong> would be</p>\n\n<pre><code>public static int fact(x, running_total=1) {\n    if (x==1) {\n        return running_total;\n    } else {\n        return fact(x-1, running_total*x);\n    }\n}\n\n</code></pre>\n\n<ol>\n<li><strong>Substituting n=4</strong> </li>\n</ol>\n\n<pre><code>public static int fact(4, running_total=1) {\n    if (x==1) {\n        return running_total;\n    } else {\n        return fact(4-1, running_total*4);\n    }\n}\n</code></pre>\n\n<p><code>If</code> loop fails so it goes to <code>else</code> loop\nso it returns <code>fact(3, 4)</code></p>\n\n<ol start="2">\n<li><p>In stack memory, we have <code>fact(3, 4)</code></p>\n\n<p><strong>Substituting n=3</strong></p></li>\n</ol>\n\n<pre><code>public static int fact(3, running_total=4) {\n    if (x==1) {\n        return running_total;\n    } else {\n        return fact(3-1, 4*3);\n    }\n}\n</code></pre>\n\n<p><code>If</code> loop fails so it goes to <code>else</code> loop</p>\n\n<p>so it returns <code>fact(2, 12)</code></p>\n\n<ol start="2">\n<li><p>In stack memory, we have <code>fact(2, 12)</code></p>\n\n<p><strong>Substituting n=2</strong></p></li>\n</ol>\n\n<pre><code>public static int fact(2, running_total=12) {\n    if (x==1) {\n        return running_total;\n    } else {\n        return fact(2-1, 12*2);\n    }\n}\n</code></pre>\n\n<p><code>If</code> loop fails so it goes to <code>else</code> loop</p>\n\n<p>so it returns <code>fact(1, 24)</code></p>\n\n<ol start="3">\n<li><p>In stack memory, we have <code>fact(1, 24)</code></p>\n\n<p><strong>Substituting n=1</strong></p></li>\n</ol>\n\n<pre><code>public static int fact(1, running_total=24) {\n    if (x==1) {\n        return running_total;\n    } else {\n        return fact(1-1, 24*1);\n    }\n}\n</code></pre>\n\n<p><code>If</code> loop is true</p>\n\n<p>so it returns <code>running_total</code></p>\n\n<p>The output for <code>running_total = 24</code></p>\n\n<p>Finally, the result of <strong>fact(4,1) = 24</strong></p>\n\n<p><a href="https://i.stack.imgur.com/FkcU1.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/FkcU1.jpg" alt="enter image description here"></a></p>\n'}, {'answer_id': 54601924, 'author': 'Al Sweigart', 'author_id': 1893164, 'author_profile': 'https://Stackoverflow.com/users/1893164', 'pm_score': 3, 'selected': False, 'text': "<p>A <em>tail recursive</em> function is a recursive function where the last operation it does before returning is make the recursive function call. That is, the return value of the recursive function call is immediately returned. For example, your code would look like this:</p>\n\n<pre><code>def recursiveFunction(some_params):\n    # some code here\n    return recursiveFunction(some_args)\n    # no code after the return statement\n</code></pre>\n\n<p>Compilers and interpreters that implement <em>tail call optimization</em> or <em>tail call elimination</em> can optimize recursive code to prevent stack overflows. If your compiler or interpreter doesn't implement tail call optimization (such as the CPython interpreter) there is no additional benefit to writing your code this way.</p>\n\n<p>For example, this is a standard recursive factorial function in Python:</p>\n\n<pre><code>def factorial(number):\n    if number == 1:\n        # BASE CASE\n        return 1\n    else:\n        # RECURSIVE CASE\n        # Note that `number *` happens *after* the recursive call.\n        # This means that this is *not* tail call recursion.\n        return number * factorial(number - 1)\n</code></pre>\n\n<p>And this is a tail call recursive version of the factorial function:</p>\n\n<pre><code>def factorial(number, accumulator=1):\n    if number == 0:\n        # BASE CASE\n        return accumulator\n    else:\n        # RECURSIVE CASE\n        # There's no code after the recursive call.\n        # This is tail call recursion:\n        return factorial(number - 1, number * accumulator)\nprint(factorial(5))\n</code></pre>\n\n<p>(Note that even though this is Python code, the CPython interpreter doesn't do tail call optimization, so arranging your code like this confers no runtime benefit.)</p>\n\n<p>You may have to make your code a bit more unreadable to make use of tail call optimization, as shown in the factorial example. (For example, the base case is now a bit unintuitive, and the <code>accumulator</code> parameter is effectively used as a sort of global variable.)</p>\n\n<p>But the benefit of tail call optimization is that it prevents stack overflow errors. (I'll note that you can get this same benefit by using an iterative algorithm instead of a recursive one.)</p>\n\n<p>Stack overflows are caused when the call stack has had too many frame objects pushed onto. A frame object is pushed onto the call stack when a function is called, and popped off the call stack when the function returns. Frame objects contain info such as local variables and what line of code to return to when the function returns.</p>\n\n<p>If your recursive function makes too many recursive calls without returning, the call stack can exceed its frame object limit. (The number varies by platform; in Python it is 1000 frame objects by default.) This causes a <em>stack overflow</em> error. (Hey, that's where the name of this website comes from!)</p>\n\n<p>However, if the last thing your recursive function does is make the recursive call and return its return value, then there's no reason it needs to keep the current frame object needs to stay on the call stack. After all, if there's no code after the recursive function call, there's no reason to hang on to the current frame object's local variables. So we can get rid of the current frame object immediately rather than keep it on the call stack. The end result of this is that your call stack doesn't grow in size, and thus cannot stack overflow.</p>\n\n<p>A compiler or interpreter must have tail call optimization as a feature for it to be able to recognize when tail call optimization can be applied. Even then, you may have rearrange the code in your recursive function to make use of tail call optimization, and it's up to you if this potential decrease in readability is worth the optimization.</p>\n"}, {'answer_id': 56460840, 'author': 'Rohit Garg', 'author_id': 6234459, 'author_profile': 'https://Stackoverflow.com/users/6234459', 'pm_score': 3, 'selected': False, 'text': '<p>Tail Recursion is pretty fast as compared to normal recursion.\nIt is fast because the output of the ancestors call will not be written in stack to keep the track.\nBut in normal recursion all the ancestor calls output written in stack to keep the track.</p>\n'}, {'answer_id': 64956968, 'author': 'Hari', 'author_id': 216562, 'author_profile': 'https://Stackoverflow.com/users/216562', 'pm_score': 2, 'selected': False, 'text': "<p>A function is tail recursive if each recursive case consists <em>only</em> of a call to the function itself, possibly with different arguments.  Or, tail recursion is <em>recursion with no pending work</em>.  Note that this is a programming-language independent concept.</p>\n<p>Consider the function defined as:</p>\n<pre><code>g(a, b, n) = a * b^n\n</code></pre>\n<p>A possible tail-recursive formulation is:</p>\n<pre><code>g(a, b, n) | n is zero = a\n           | n is odd  = g(a*b, b,   n-1)\n           | otherwise = g(a,   b*b, n/2)\n</code></pre>\n<p>If you examine each RHS of <code>g(...)</code> that involves a recursive case, you'll find that the whole body of the RHS is a call to <code>g(...)</code>, and <em>only</em> that.  This definition is <em>tail recursive</em>.</p>\n<p>For comparison, a non-tail-recursive formulation might be:</p>\n<pre><code>g'(a, b, n) = a * f(b, n)\nf(b, n) | n is zero = 1\n        | n is odd  = f(b, n-1) * b\n        | otherwise = f(b, n/2) ^ 2\n</code></pre>\n<p>Each recursive case in <code>f(...)</code> has some <em>pending work</em> that needs to happen after the recursive call.</p>\n<p>Note that when we went from <code>g'</code> to <code>g</code>, we made essential use of associativity\n(and commutativity) of multiplication.  This is not an accident, and most cases where you will need to transform recursion to tail-recursion will make use of such properties: if we want to eagerly do some work rather than leave it pending, we have to use something like associativity to prove that the answer will be the same.</p>\n<p>Tail recursive calls can be implemented with a backwards jump, as opposed to using a stack for normal recursive calls.  Note that detecting a tail call, or emitting a backwards jump is usually straightforward.  However, it is often hard to rearrange the arguments such that the backwards jump is possible.  Since this optimization is not free, language implementations can choose not to implement this optimization, or require opt-in by marking recursive calls with a 'tailcall' instruction and/or choosing a higher optimization setting.</p>\n<p>Some languages (e.g. Scheme) do, however, require <em>all</em> implementations to optimize tail-recursive functions, maybe even all calls in tail position.</p>\n<p>Backwards jumps are usually abstracted as a (while) loop in most imperative languages, and tail-recursion, when optimized to a backwards jump, is isomorphic to looping.</p>\n"}, {'answer_id': 71566598, 'author': 'Yilmaz', 'author_id': 10262805, 'author_profile': 'https://Stackoverflow.com/users/10262805', 'pm_score': 3, 'selected': False, 'text': '<ul>\n<li>Tail Recursive Function is a recursive function in which recursive call is the last executed thing in the function.</li>\n</ul>\n<p>Regular recursive function, we have stack and everytime we invoke a recursive function within that recursive function, adds another layer to our call stack. In normal recursion\nspace: <code>O(n)</code> tail recursion makes space complexity from</p>\n<pre><code>O(N)=&gt;O(1)\n</code></pre>\n<ul>\n<li><p>Tail call optimization means that it is possible to call a function from another function without growing the call stack.</p>\n</li>\n<li><p>We should write tail recursion in recursive solutions. but certain languages do not actually support the tail recursion in their engine that compiles the language down. since ecma6, there has been tail recursion that was in the specification. BUt none of the engines that compile js have implemented tail recursion into it. you wont achieve O(1) in js, because the compiler itself does not know how to implement this tail recursion. As of January 1, 2020 Safari is the only browser that supports tail call optimization.</p>\n</li>\n<li><p>Haskell and Java have tail recursion optimization</p>\n</li>\n</ul>\n<h2>Regular Recursive Factorial</h2>\n<pre><code>function Factorial(x) {\n  //Base case x&lt;=1\n  if (x &lt;= 1) {\n    return 1;\n  } else {\n    // x is waiting for the return value of Factorial(x-1)\n    // the last thing we do is NOT applying the recursive call\n    // after recursive call we still have to multiply.\n    return x * Factorial(x - 1);\n  }\n}\n</code></pre>\n<p>we have 4 calls in our call stack.</p>\n<pre><code>Factorial(4); // waiting in the memory for Factorial(3)\n4 * Factorial(3); //  waiting in the memory for Factorial(2)\n4 * (3 * Factorial(2)); //  waiting in the memory for Factorial(1)\n4 * (3 * (2 * Factorial(1)));\n4 * (3 * (2 * 1));\n</code></pre>\n<ul>\n<li>We are making 4 Factorial() calls, space is O(n)</li>\n<li>this mmight cause Stackoverflow</li>\n</ul>\n<h2>Tail Recursive Factorial</h2>\n<pre><code>function tailFactorial(x, totalSoFar = 1) {\n  //Base Case: x===0. In recursion there must be base case. Otherwise they will never stop\n  if (x === 0) {\n    return totalSoFar;\n  } else {\n    // there is nothing waiting for tailFactorial to complete. we are returning another instance of tailFactorial()\n    // we are not doing any additional computaion with what we get back from this recursive call\n    return tailFactorial(x - 1, totalSoFar * x);\n  }\n}\n</code></pre>\n<ul>\n<li>We dont need to remember anything after we make our recursive call</li>\n</ul>\n'}]
['https://Stackoverflow.com/questions/33923', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2045/']