The author is a snake addicted to Python who can't stop himself from posting Python highlights and interesting examples on Jane's for improvement.
caudal recursion
We call a recursive function tail-recursive if all calls of the recursive form occur at the end of the function. A recursive call is tail recursive when it is the last statement executed in the entire function body and its return value is not part of the expression. The characteristic of a tail-recursive function is that it does not have to do anything during the return process, which is important because most modern compilers take advantage of this characteristic to automatically generate optimized code.
(From Some Degree of Unspeakability)
The following is the author's personal understanding: the calculated value exists within the function (of course, more than just tail recursion) is its calculation method, so that you do not have to go on the stack to create a new one, which greatly saves space. The last result returned in a function call is simply a recursive function call (or return result) is the tail recursion.
an actual example
The examples are still the same as in the author's previous article, which the reader is advised to readPython -- Recursion
1. factorial
Regular recursive factorial:
def factorial(n):
if n == 0:
return 1
return factorial(n - 1) * n
Let's look at the execution process:
factorial(4)
factorial(3) * 4
factorial(2) * 3 * 4
factorial(1) * 2 * 3 * 4
factorial(0) * 1 * 2 * 3 * 4
1 * 1 * 2 * 3 * 4
1 * 2 * 3 * 4
2 * 3 * 4
6 * 4
24
But if the above function is written in the following form:
def factorial(n, acc=1):
if n == 0:
return acc
return factorial(n - 1, n * acc)
Let's look at the execution process again:
factorial(4, 1)
factorial(3, 4)
factorial(2, 12)
factorial(1, 24)
factorial(0, 24)
24
It's intuitively obvious that this time, instead of generating a series of progressively more intermediate variables when called recursively, the factorial function stores the state in the variable acc. This form of recursion is called tail recursion.
2. Fibonacci series
Regular recursive Fibonacci series:
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
And tail recursion:
def fib_tail(n, r, t):
if n == 1:
return r
else:
return fib_tail(n - 1, t, r + t)
All of a sudden it's full of compulsion and a lot more efficient, so why not!
summarize
As you can see, on each recursive call, a temporary variable is created, causing the process memory footprint to increase a bit. This can lead to the famous stack overflow error when executing code with deeper levels of recursion, in addition to needless memory waste.
This is the whole content of this article.