Recursive function in simple english [duplicate]

This question already has answers here: 开发者_StackOverflow Closed 11 years ago.

Possible Duplicate:

Understanding recursion

Can anyone explain me what does actually a recursive function does in simple english?

It will be good if you say with an example.

---

Three words - It Calls Itself.

---

It's a function which calls itself, usually with a different set of parameters in each iteration. In most cases, it will call itself repeatedly, until there is a set of input parameters which will "stop it".

And if you don't make sure that a certain set of parameter stops it, it will call itself forever, or you will end up with a stack overflow. :-)

A simple example in C# would be something like:

void PrintPositiveNumbersBackwards(int number)
{
    // this is a condition which stops the recursion
    if (number == 0)
       return;

    Console.WriteLine(number);

    // this is where the function calls itself,
    // with a different (smaller) input parameter
    PrintPositiveNumbersBackwards(number - 1);
}

---

From the Wikipedia:

Recursion in plain English

Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be 'recursive'.

To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps that are to be taken based on a set of rules. The running of a procedure involves actually following the rules and performing the steps. An analogy might be that a procedure is like a cookbook in that it is the possible steps, while running a procedure is actually preparing the meal.

Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure. For instance, a recipe might refer to cooking vegetables, which is another procedure that in turn requires heating water, and so forth. However, a recursive procedure is special in that (at least) one of its steps calls for a new instance of the very same procedure. This of course immediately creates the danger of an endless loop; recursion can only be properly used in a definition if the step in question is skipped in certain cases so that the procedure can complete. Even if properly defined, a recursive procedure is not easy for humans to perform, as it requires distinguishing the new from the old (partially executed) invocation of the procedure; this requires some administration of how far various simultaneous instances of the procedures have progressed. For this reason recursive definitions are very rare in everyday situations. An example could be the following procedure to find a way through a maze. Proceed forward until reaching either an exit or a branching point (a dead end is considered a branching point with 0 branches). If the point reached is an exit, terminate. Otherwise try each branch in turn, using the procedure recursively; if every trial fails by reaching only dead ends, return on the path that led to this branching point and report failure. Whether this actually defines a terminating procedure depends on the nature of the maze: it must not allow loops. In any case, executing the procedure requires carefully recording all currently explored branching points, and which of their branches have already been exhaustively tried. Recursive humor

A common joke is the following "definition" of recursion.

Recursion

    See "Recursion".

A variation on this joke is:

Recursion

    If you still don't get it, see: "Recursion".

which actually does terminate, as soon as the reader "gets it".

---

A recursive function is defined in terms of itself. In real terms it means it calls itself in the implementation.

Simple examples define a series in terms of previous values with a stopping point.

long factorial(long n) {
    if (n <= 1) // stopping point.
      return 1;
    return n * factorial(n - 1);
}

long fibonacci(long n) {
    if (n <= 2) // stopping point.
      return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Recursive functions can be an elegant way of breaking up a problem, and representing a mathematical definition however in most Imperative programming languages like the ones you mention, using a loop is more efficient.

long factorial(long n) {
   long product = 1;
   for(long i = 2; i <= n; i++) 
       product *= i;
   return product;
}

long fibonacci(long n) {
   long a = 0, b = 1, c = 1;
   for(int i=1; i<n; i++) {
      a = b;
      b = c;
      c = a + b;
   }
   return c;
}

---

A recursive function is defined in terms of itself but applied to "simpler arguments or data". If this "simpler data" is trivial, the function can be evaluated without calling itself, thus breaking the recursion, which would be infinite otherwise. A classical example is the factorial function:

n! = (n-1)! * n, if n > 0    (recursion case)
0! = 1                       (termination)

---

A recursive function calls itself. However this can lead to sort of "infinite loops" (and stack overflows). So, once it reached the desired level of recursion, the function needs to test a condition and "exit" by not making another call at itself.

The following function calls itself 10 times.

int level = 0;
int call_me() {
  if( level < 10 )
    level++;
    call_me();
  else
    ; // "Exit here"
}