Search forums

Forums

Export thread

Recursion

Apr 23, 2012#1

Covar

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.

Code:

int factorial(int n) {
    if(n <= 1)
        return 1;
    else
        return n * factorial(n-1);
}

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.

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;
}

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.

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);
}

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.

Apr 23, 2012#2

General Specific

To understand recursion you must first understand recursion.

Apr 23, 2012#3

Allen who is Quiet

Your mother is so overweight, the recursive algorithm for calculating her mass causes a stack overflow.

Apr 23, 2012#4

Bowielee

I see what you did there...

For the record, I have the biggest love/hate relationship with recursion. It's mostly working with stacks and linked lists where I hate it the most.

In practice

class Hw7_2
{
public static void main(String[] args)
{
int[] array = {56, 23, 78, 91, 2, 45, 11, 37, 10, 27, 82, 13, 90}; //initialize unsorted array
int[] sorted = new int[array.length]; //create empty array for sorted array
printArray(array); //print unsorted array
sort(array,0,array.length-1); //call sorting method
for(int i=0;i<array.length;i++) //loop to input sorted array
sorted=array;
printArray(sorted); //print sorted array
}
public static void sort(int[] a, int s, int e) //sort method
{
if(s<e) //termination condition, end if start index is == to end index
{
int index = partition(a,s,e); //get index from partition method
if (index>1) //condition to check if subarray is greater than 1
sort(a,s,index-1); //recursive call incrementing end index down
if (index+1<e) //check if start of subaray is less than end of array
sort(a,index+1,e); //recursive call incrementing starting index up
}
}
public static int partition(int[] a, int s, int e) //partition method
{
int indexNum = a; //set placeholder for index number
while(0<1) //infinite loop until return condition met
{
while(a<indexNum) //increment starting index up if start less than index number
s++;
while(a[e]>indexNum) //increment ending index down if start less than index number
e--;
if(s<e) //condition to swap number
{
int temp=a[e]; //placeholder for swapping places of numbers
a[e]=a; //swap last in subarray with first in subarray
a=temp; //swap first in sub array with placeholder number
}
else
{
return e; //terminate loop and return ending index of subarray
}
}
}
public static void printArray(int[] a) //print method
{
for(int i=0;i<a.length;i++)
System.out.print(a+" ");
System.out.println();
}
}

Also, I can't believe that I ever thought that this program was hard.

Apr 23, 2012#5

bhamv3

I remember reading somewhere that in a certain programming textbook, if you look up "recursion" in the index, it also lists the index page that the word "recursion" shows up on. So, theoretically, you could recursively look up recursion in the index, infinitely.

Apr 24, 2012#6

David

Covar said:
A recursive function is a function that references itself in it's body.

Apr 24, 2012#7

Bowielee

This is quite conceivably the most nerdy thing I've ever done.

Apr 24, 2012#8

PatrThom

Hey, recursion is freakin' awesome. I love collapsing code. I just hate when I forget to include the exit condition.

--Patrick

Apr 26, 2012#9

fade

Having spent the last 2 months trying to decipher someone else's code, let me tell you: I hate anything that reduces readability. As long as it's absolutely clear it recurses.

Apr 26, 2012#10

Bowielee

People who don't annotate code are of the DEVIL.

May 30, 2012#11

Eriol

Check out the index in the K&R "The C Programming Language" book. Look up recursion, and note the page numbers it references.

Jun 4, 2012#12

General Specific

Bowielee said:
View attachment 5669
This is quite conceivably the most nerdy thing I've ever done.

Hey, it's almost still on topic, it certainly repeats enough.

Jun 4, 2012#13

strawman

I made use of recursion last week. My client wanted to print receipts using a template, and wanted to have repeating sections inside the template. I found out that they wanted to put repeating sections inside repeating sections once I looked at the example receipt, so I made the code call itself when it encountered a repeating section, and only feed the repeating section to itself. They can now nest the repeating sections as deeply as they want and it'll work as intended.

Example template:

?storename? ?date?
!itemrepeat!?quantity? ?description? ?priceeach? ?linetotal?
!serialnumberrepeat!?serialnumber?!endserialnumbrepeat!!enditemrepeat!

Subtotal: ?subtotal?
Tax: ?tax?
Total: ?total?

Then a receipt, once all the data was filled in, might look like this:

Halforums store 12/3/2012
6 XBox360. $150.00. $900.00
785634
653925
835297
839463
821990
963285
1 COD4 $35.00 $35.00
1 Coupon. $ -45.00. $ -45.00

Subtotal: $890.00
Tax: $89.00
Total: $979.00

So they can have as many items in the receipt as they want without specifically writing an item line for each one in the template, and each item can have as many, or no, serials as needed without writing a serial line for each possible serial they might print under a given item. In this example the code would be called on the whole thing, then on the itemrepeat section, then on each serial section, and as the data was processesed it would return on each level back up until all the data was processed and the whole thing would return with the filled in receipt data.

So there are real world uses for recursion beyond conceptual algorithms, math, and computer science programming assignments. It's not something to be used without due care, though, the are a number of pitfalls...

Jun 4, 2012#14

PatrThom

PatrThom said:
I just hate when I forget to include the exit condition.

PatrThom said:

I just hate when I forget to include the exit condition.

PatrThom said:

I just hate when I forget to include the exit condition.

PatrThom said:

I just hate when I forget to include the exit condition.

PatrThom said:

I just hate when I forget to include the exit condition.

PatrThom said:

Dammit!

Click to expand...

Click to expand...

Click to expand...

Click to expand...

Click to expand...

--Patrick

Jun 8, 2012#15

fade

I am a huge code nerd. I've been coding since like the mid 80s (woohoo BASIC). I have had the need to write one recursive function in all that time, despite the fact that coding books lavish attention on them. Mine is a finite element mesh search routine that needs to grow organically from a start point. It makes logical sense to check the node, then check all the connected nodes, then all nodes connected to that node, etc.

Jun 8, 2012#16

strawman

The fun thing about recursion is that you can almost always perform the same work using a different technique, and recursion is a little harder to understand and apply correctly. So generally people choose the non-recursive path.

Jun 8, 2012#17

Eriol

stienman said:
The fun thing about recursion is that you can almost always perform the same work using a different technique, and recursion is a little harder to understand and apply correctly. So generally people choose the non-recursive path.

I'd say rather that you can almost always perform an iterative task with recursion, but it'll be harder to understand, but there's a few things that you can do with recursion that are much harder to understand if you do it with anything like an iterative approach (the amount of state variables you need to keep track of become insane). fade's mention of tree/graph traversal is actually one of those that's almost always clearer with recursion. The other thing is often divide-and-conquer approaches to problems, where you do the same thing, but with a sub-set (quick sort is the most commonly-known one of those).

Basically, if you try either approach to a problem and it ends up looking like "wtf did I just do?" then you're probably supposed to use the other one.

Jun 8, 2012#18

evilmike

Forums