• Recursion It is legal for one function to call another; it is also legal for a function to call itself. It may not be obvious why what is a good thing, but it turns out to be one of the most mag...

Recursion
It is legal for one function to call another; it is also legal for a function to call itself. It may not be obvious why what is a good thing, but it turns out to be one of the most magical things a program can do. For example: If a recursion never reaches a base case, it goes on making recursive calls forever, and the program never terminates. This is known as infinite recursion, and it is generally not a good idea. In most programming environments, a program with infinite recursion does not really run forever. Python reports an error message when the maximum recursion depth is reached: When the error occurs, there are 1000 recurse frames on the stack.

form Thinking in Python

转载于:https://www.cnblogs.com/ryansunyu/p/3702828.html
展开全文 • void hanoi(int n, char x, char y, char z) { if (n == 1) printf("%c->%c\n", x, z); else { hanoi(n - 1, x, z, y); printf("%c->%c\n", x, z); hanoi(n - 1, y, x, z);......


void hanoi(int n, char x, char y, char z)
{
if (n == 1)
printf("%c->%c\n", x, z);
else
{
hanoi(n - 1, x, z, y);
printf("%c->%c\n", x, z);
hanoi(n - 1, y, x, z);

}
}


转载于:https://www.cnblogs.com/KIROsola/p/11402773.html
展开全文 • Recursion1. IntroductionRecursion is a technique that allows us to break down a problem into one or more subproblems that are similar in form to the original problem.  2. Example: The ...


Recursion

1. Introduction
Recursion is a technique that allows us to break down a problem into one or more subproblems that are similar in form to the original problem.

2. Example: The Factorial
Recall that factorial, which is written n!, has the following definition:
n! = 1 * 2 * 3 * .... * (n-2) * (n-1) * n
We can use this definition to write:
int fact(int n) {
int i;
int result;

result = 1;
for (i = 1; i <= n; i++) {
result = result * i;
}
return result;
}
We can write a function that uses recursion as follows:
int fact(int n) {
if (n == 1) return 1;
return n * fact(n - 1);
}
Comparing the two versions:
The iterative version has two local variables; the recursive version has none.
The iterative version has three statements; the recursive version has one.
The iterative version must save the solution in an intermediate variable before it can be returned; the recursive version calculates and returns its result as a single expression.
Recursion simplifies the fact function! It does so by making the computer do more work, so that you can do less work.

3. Definitions
The recursive functions are characterized based on: whether the function calls itself or not (direct or indirect recursion).
whether there are pending operations at each recursive call (tail-recursive or not).
the shape of the calling pattern -- whether pending operations are also recursive (linear or tree-recursive).
Direct Recursion:
A function is directly recursive if it contains an explicit call to itself. For example, the function
int foo(int x) {

if (x <= 0) return x;

return foo(x - 1);
}
includes a call to itself, so it's directly recursive. The recursive call will occur for positive values of x.
Indirect Recursion:
A function foo is indirectly recursive if it contains a call to another function which ultimately calls foo.
The following pair of functions is indirectly recursive. Since they call each other, they are also known as mutually recursive functions.
int foo(int x) {

if (x <= 0) return x;

return bar(x);
}

int bar(int y) {
return foo(y - 1);
}
Tail Recursion:
A recursive function is said to be tail recursive if there are no pending operations to be performed on return from a recursive call.
Tail recursive functions are often said to "return the value of the last recursive call as the value of the function." Tail recursion is very desirable because the amount of information which must be stored during the computation is independent of the number of recursive calls. Some modern computing systems will actually compute tail-recursive functions using an iterative process.
The "infamous" factorial function fact is usually written in a non-tail-recursive manner:
int fact (int n) { /* n >= 0 */

if (n == 0)  return 1;

return n * fact(n - 1);
}
Notice that there is a "pending operation," namely multiplication, to be performed on return from each recursive call. Whenever there is a pending operation, the function is non-tail-recursive. Information about each pending operation must be stored, so the amount of information is not independent of the number of calls.
The factorial function can be written in a tail-recursive way:
int fact_aux(int n, int result) {

if (n == 1) return result;

return fact_aux(n - 1, n * result)
}

int fact(n) {

return fact_aux(n, 1);
}
The "auxiliary" function fact_aux is used to keep the syntax of fact(n) the same as before. The recursive function is really fact_aux, not fact. Note that fact_aux has no pending operations on return from recursive calls. The value computed by the recursive call is simply returned with no modification. The amount of information which must be stored is constant (the value of n and the value of result), independent of the number of recursive calls.
Linear and Tree Recursion:
Another way to characterize recursive functions is by the way in which the recursion grows. The two basic ways are "linear" and "tree."
A recursive function is said to be linearly recursive when no pending operation involves another recursive call to the function.
For example, the "infamous" fact function is linearly recursive. The pending operation is simply multiplication by a scalar, it does not involve another call to fact.
A recursive function is said to be tree recursive (or non-linearly recursive) when the pending operation does involve another recursive call to the function.
The Fibonacci function fib provides a classic example of tree recursion. The Fibonacci numbers can be defined by the rule:
fib(n) = 0  if n is 0,
= 1  if n is 1,
= fib(n-1) + fib(n-2) otherwise
For example, the first seven Fibonacci numbers are
Fib(0) = 0
Fib(1) = 1
Fib(2) = Fib(1) + Fib(0) = 1
Fib(3) = Fib(2) + Fib(1) = 2
Fib(4) = Fib(3) + Fib(2) = 3
Fib(5) = Fib(4) + Fib(3) = 5
Fib(6) = Fib(5) + Fib(4) = 8
This leads to the following implementation:
int fib(int n) { /* n >= 0 */

if (n == 0) return 0;

if (n == 1) return 1;

return  fib(n - 1) + fib(n - 2);
}
Notice that the pending operation for the recursive call is another call to fib. Therefore fib is tree-recursive.

4. Converting Recursive Functions to be Tail Recursive
A non-tail recursive function can often be converted to a tail-recursive function by means of an "auxiliary" parameter. This parameter is used to form the result. The idea is to attempt to incorporate the pending operation into the auxiliary parameter in such a way that the recursive call no longer has a pending operation. The technique is usually used in conjunction with an "auxiliary" function. This is simply to keep the syntax clean and to hide the fact that auxiliary parameters are needed.
For example, a tail-recursive Fibonacci function can be implemented by using two auxiliary parameters for accumulating results. It should not be surprising that the tree-recursive fib function requires two auxiliary parameters to collect results; there are two recursive calls. To compute fib(n), call fib_aux(n 1 0)
int fib_aux(int n, int next, int result) {

if (n == 0) return result;
return fib_aux(n - 1, next + result, next);
}
The tree recursive fib() method is "Big O 2^n" (O(2^n)) algorithm. In other words as n increases the problem size roughly doubles. On the other hand, a linearly recursive algorithm would be O(n). In other words, the amount of work required roughly increases linearly.
References: Thomas A. Anastasio, Richard Chang.


展开全文  function parameters tree
• C++
• Java
• <div><p>Although I love recursion and Ramer-Douglas-Peucker is naturally defined as a recursion, this is quite inefficient in Python and leads often to errors like <code>RecursionError: maximum ...
• Recursion Algorithm <p><strong>Submission Type Algorithm/Recursion/ <p><strong>Submission Description Describe the Algo/Recursion <p><strong>Submission Directory Algorithm/Recursion/ <p><strong>...
• <ul><li>Wrote new specs and PE tests for <code>detect_recursion</code>.</li><li>Moved the extra methods from <code>Thread</code> to <code>Truffle::ThreadOperations</code>.</li><li>Replaced <code>...
• <div><p>Infinite recursion is crashed, no SystemStackError exception ~</p><p>该提问来源于开源项目：mruby/mruby</p></div>
• <div><p>Allows the user in the config to specify to use zfs snapshot recursion option other than using Perl to recursively take snapshots. So your config would look like <h6></h6> [pool4/zones/zone1]...
• <div><p>Hey, i want to add some recursion problems and their solutions ,can you assign me that task ?</p><p>该提问来源于开源项目：sahilbansal17/Competitive_Coding</p></div>
• <div><p>Fixes a deep recursion in logging that was surfaced by JaCoCo runs (which have different errors, hence different logging) <p>Also, cleans up duplication in build.xml for JaCoCo targets</p><p>...
• <div><p>Infinite recursion can happen using with (obj) instance_create(x, y, obj); <p>This can also happen when creating same object types using things like key presses and such.</p><p>该提问来源于...
• too much recursion" (v2.0.0-rc7). <p>https://jsfiddle.net/wuc48347/</p> <p>Here's how it should work: https://jsfiddle.net/q7hsuqmp/1/ (using <a href="https://www.npmjs.com/package/decca">...
• <div><p>I understand that the non-recursion is by design, but I have an use case where it would be pretty useful. In a spa, I'm receiving a complex object from an API, and I want to be able to ...
• <div><p>I tried to generate private key ...RuntimeError: maximum recursion depth exceeded in cmp root:/mnt/hgfs/shf/RsaCtfTool# <p>Maybe i did something wrong, but i'm sure that my data is correct. ...
• 50 intervals, the recursion depth of python is reached while balancing the tree. Minimum working example: <pre><code> python from intervaltree import Interval, IntervalTree from numpy import sort from...
• That caused an infinite recursion in <code>_setAttr</code> (and subsequent crash) because <code>window</code> has a few self-referencing properties like <code>window.window, <code>window.self, <code>...
• Java
• C#
• Tail recursive will return the result immediately when the recursion reach the base case. However, for normal recursion, when it reaches the base case it will return to the previous call again and a
Tail recursive will return the result immediately when the recursion reach the base case.
However, for normal recursion, when it reaches the base case it will return to the previous call
again and again in order to get the final result.
Examples.
public class FactRecur {

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(normalRecurFac(4));
System.out.println(tailRecurFac(4, 1));
}

public static int normalRecurFac(int num) {
if (num == 1) return num;
return num * normalRecurFac(num-1);
}

public static int tailRecurFac(int num, int res) {
if (num == 1) return res;
return tailRecurFac(num-1, res * num);
}
}
展开全文 • Traditional Recursion Perform recursive call first, and the do the calculation. public class FibRecusion { public long fib(long index) { if (index == 0 || index == 1) { ...  ...