If you already understand recursion click here otherwise read on.
What is Recursion?
Recursion is an incredibly useful programming tool. A recursive function is a function that references itself in it's body.
But How is it Useful?
This technique allows you to break down a large problem into multiple identical smaller problems, increasing the efficiency as your datasets grow. A prime and common example is when sorting groups of items. Without recursion you might go about this linearly.
I know what you're thinking. But Covar, I only have a few items to sort and it's not the 1970s anymore. Sure you think that, and you can be right. The problem here is that it doesn't scale well. if you have, say, 100,000 or more items you'll be waiting a while. The answer here is recursion. By breaking up the items into smaller and smaller lists before sorting you drastically reduce the amount of effort needed to sort.
The above code is an implementation of a quick sort. Courtesy of Lars Vogel
What is the downside to using recursion?
Well for one you have to have a good mental grasp of what goes on in recursion. Until it clicks it can be hard to read and only serve to make the code confusing. You can also get stuck. A recursive method or function needs to have an exit condition, a way for it to stop calling itself and allow the original call to finish. Unlike a loop, failure to exit will not cause your program to run indefinitely. No infinite recursion causes your application to bomb out via a stack overflow (Oversimplified explanation: the call stack is memory allocated to a program to run in, when you exceed that you get a stack overflow). This is because the way recursion works, when you run a function it goes onto the call stack. When you run a recursive function each new call in the function definition creates a new copy on the stack. As your function starts hitting it's end condition the stack empties out.
I still don't get it.
That's okay. You can click here for clarification.
What is Recursion?
Recursion is an incredibly useful programming tool. A recursive function is a function that references itself in it's body.
Code:
int factorial(int n) {
if(n <= 1)
return 1;
else
return n * factorial(n-1);
}This technique allows you to break down a large problem into multiple identical smaller problems, increasing the efficiency as your datasets grow. A prime and common example is when sorting groups of items. Without recursion you might go about this linearly.
Code:
int [] sort(int[] items) {
boolean madeSwap;
do {
madeSwap = false; // reset the exit condition of our do/while loop
for(int i=0; i<items.length-1;i++) {
if(items[i] > items[i+1]) {
swap(items[i],items[i+1]);
madeSwap = true; // the list wasn't completely sorted so we'll have to go back through
}
}
} while(madeSwap) // keep going until we've ensure the items are sorted
return items;
}
Code:
int [] items = new int[100000];
void sort(int low, int high) {
int i = low, j = high;
int pivot = numbers[low + (high-low)/2];
while (i <= j) {
while (numbers[i] < pivot) {
i++;
}
while (numbers[j] > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
i++;
j--;
}
}
// Recursion
if (low < j)
sort(low, j);
if (i < high)
sort(i, high);
}What is the downside to using recursion?
Well for one you have to have a good mental grasp of what goes on in recursion. Until it clicks it can be hard to read and only serve to make the code confusing. You can also get stuck. A recursive method or function needs to have an exit condition, a way for it to stop calling itself and allow the original call to finish. Unlike a loop, failure to exit will not cause your program to run indefinitely. No infinite recursion causes your application to bomb out via a stack overflow (Oversimplified explanation: the call stack is memory allocated to a program to run in, when you exceed that you get a stack overflow). This is because the way recursion works, when you run a function it goes onto the call stack. When you run a recursive function each new call in the function definition creates a new copy on the stack. As your function starts hitting it's end condition the stack empties out.
I still don't get it.
That's okay. You can click here for clarification.
