What is recursion?

Question

Possible duplicate:
Examples of recursive functions

I am trying to explore recursion in programming as a concept (although I specifically study Java), and this is what I understood in order to better understand:

In real life, for example, recursion is when we put two mirrors on top of each other, and the images created between them are recursive.

But I do not get this algorithm in programming? Can someone give me a simplified example to understand recursion?

Answer 1

Basically, a function is recursive when

• The function has a simple base register, and when
• All other cases have rules that are reduced to the main case.

As an example, to calculate the factorial:

public static long factorial(int i) { // This is the base case if(i == 0) { return 1; } else { // This reduces the problem to something closer to the base case return i * factorial(i - 1); } } 

Answer 2

Recursion is a programming method in which a method can call itself part of its calculation (sometimes you can have several methods), then the methods will usually call each other in a circular fashion).

A popular example is the calculation of Fibonacci numbers :

 public static long fib(int n) { if (n <= 1) return n; else return fib(n-1) + fib(n-2); } 

The two basic components are the base case ( n<=1 in the example) and the recursive case.

When creating a recursive algorithm, you need to consider the base case and how, using the recursive case, you will be taken to the base case (otherwise you will end the infinite recursion and duplicate the stack).

Answer 3

Recursive programming is a method based on the idea of mathematical induction by which a method or function re-names itself. Thus, a factorial function can be implemented as follows:

 int fact(int n) { if (n < 2) { return 1; } return n * fact(n-1); } 

Note that to ensure that the recursion completes, you must definitely handle the base register, in which you have a certain constant output for some known simple input, and you must be sure to simplify the parameters of your function for each iteration (in the above Above example, the reduction of n by 1).

Answer 4

Some computational problems can be described in such a way that the problem can be divided into smaller subtasks. Smaller subtasks are solved using the same method as the main problem. If a smaller subtask is just a smaller case of a larger problem, then this in itself can be destroyed even further.

In the end, the problem is so small that it can be solved without further destruction. This is called basic. With a basic solution, you can build a solution for a bigger problem.

Say you wanted to find ^b where a and b are positive integers. You can see that this is the same as a * a ^(b-1) . That is, ^(b-1) is a smaller problem than the original, but still requires that the same technique be solved as the original problem. To solve a ^(b-1) you see that it is a * a ^(b-2) .

And so on.

In the end, you get * a * a * ... * a ^(bb) . And we know that bb = 0 and a ⁰ = 1. Therefore, we do not need to develop this last bit, because we already know the answer. Ultimately, a ^b = a * a * a * ... * 1.

So 2 ⁴ = 2 * 2 ³ = 2 * 2 * 2 ² = 2 * 2 * 2 * 2 ¹ = 2 * 2 * 2 * 2 * 2 ⁰ = 2 * 2 * 2 * 2 * 1.

To write this program, first process the base register, and then use recursion to handle the rest.

  pow(a, b){ if(b == 0){ return 1; }else{ return a * pow(a, b - 1); } } 

It is important to note that this is just the basic idea of ​​recursion. These examples that you see in various answers, such as the problem of fibonacci numbers, are very inefficient. You can create more efficient programs using dynamic programming methods that use recursion as one of its mechanisms to solve the problem.

Answer 5

Very simple "recursive" code.

Move the top element of the list. Remove it from the list and call the code to process the top element of the list.

The roots of trees have a certain length and are divided into separate roots every 2/3 of the root. The divided parts are split into separate roots every 2/3 of the root. The divided pieces of the divided pieces are split each time, etc.

Answer 6

Recursion

A method can call itself, it is a recursion. Recursive implementations of methods are often used because they result in a compact, elegant code that is easier to understand than a corresponding implementation that does not use recursion.

The recursive programming technique knows three important rules:

• Base case: recursion has a base case. Always the first statement is conditional and has a "return".
• Subroutine: recursive calls address a subproblem that is smaller to solve in a way, so that it converges to the base case.
• No overlap: recursive calls do not handle subtasks that overlap.

In terms of performance, non-recursive solutions are faster and usually require less memory. (e.g. binary search)
But some tasks are so complex that only a recursive solution leads to (more or less understandable) code.

Example of a recursive binary search:

 public static int binSearch(int[] a, int key) { return binSearch0(a, key, 0, a.length - 1); } public static int binSearch0(int[] a, int key, int from, int to) { if (from > to) return -1; // looks strange but (from + to) / 2 can oveflow // (java bug which was active more than 10 years) int mid = from + (to - from) / 2; if (key < a[mid]) return binSearch0(a, key, from, mid - 1); else if (key < a[mid]) return binSearch0(a, key, mid + 1, to); else return mid; } 

In this example, you see all three rules (base, sub, non oberlap).
Not that in this example, recursive functions often have a start, binSearch function. Where "binSearch0" is a recursive function.