Possible Duplicate:
Examples of Recursive functions
I have been trying to research recursion in programming as a concept (though I am specifically studying Java) and this is what I got to understand the best:
In real life for example, recursion is when we put two mirrors infront of each other and the images produced between them are recursive.
But I don't get this algorithm in programming? Can someone give me a simplified example to understand recursion ?
Recursion is a programming technique where a method can call itself as part of its calculation (sometimes you can have more than one method - the methods would then normally call each other circularly).
A popular example is calculating 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 a 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 get to the base case (otherwise you end up with infinite recursion and blow the stack).
Basically, a function is recursive when
As an example, to calculate an 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);
}
}
Some computational problems can be described in such a way that the problem can be broken down to smaller subproblems. The smaller subproblems are solved using the same method as the main problem. If the smaller subproblem is just a smaller case of the bigger problem then that itself can be broken down even further.
Eventually, the problem is so small that it can be solved without further breaking down. This is known as the base case. With the solution of the base case you can then build the solution to the bigger problem.
Say you wanted to find ab where a and b are positive integers. You can see that this is the same as a * a(b-1). That is, a(b-1) is a smaller problem than the original, but still requires the same technique to solve as the original problem. To solve a(b-1) you see that it is a * a(b-2).
And so on.
Eventually you end up with a * a * a * ... * a(b-b). And we know that b-b = 0 and a0 = 1. So we do not have to work out that last bit because we already know the answer. Ultimately, ab = a * a * a * ... * 1.
So 24 = 2 * 23 = 2 * 2 * 22 = 2 * 2 * 2 * 21 = 2 * 2 * 2 * 2 * 20 = 2 * 2 * 2 * 2 * 1.
To write this program you first handle the base case then use recursion to handle everything else.
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 the various answers such a fibonacci numbers problem are very inefficient. You can build more efficient programs using dynamic programming techniques which uses recursion as one of its mechanisms for solving the problem.
Recursive programming is a technique based on the idea of mathematical induction whereby a a method or function repeatedly calls itself. As such, it's possible to implement a factorial function as follows:
int fact(int n) {
if (n < 2) {
return 1;
}
return n * fact(n-1);
}
Note that in order to ensure that the recursion terminates, you should be sure to handle a base case whereby you have a defined constant output for some known simple input, and you should be sure to make the parameters of your function simpler on each iteration (In the above example reducing n by 1).
A method can call itself, this is recursion. Recursive implementations of methods are often used, because they lead to compact elegant code, which is easier to understand than a coresponding implementation that does not use recursion.
The recursive programming technic knows three important rules (of thumb):
From view of performance non recursive solutions are faster, and usually need less memory. (e.g binary search)
But some tasks are such complex that only a recursive solution leads to a (more or less understandable) code.
Example of 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 that example you see all three rules (base, sub, non oberlap).
Not that recursive functions often have a start function, 'binSearch' in the example. Where 'binSearch0' is the recursive function.
Very simple 'recursive' code.
Handle top item of a list. Remove it from the list and call the code to handle the top item of a list.
Tree roots have a certain length and split into seperate roots every 2/3 root. The split pieces split into seperate roots every 2/3 root. The split pieces of the split pieces split every.. etc.
