[keithgarry]

Recursion is kicking my butt. I am hoping someone can walk me through an example and help me understand it. Additionally, when should recursion be used? Is it used often? Does anyone know if recursion is used in terrain editing software(displacements)?

#include <iostream>
using namespace std;
const int Len = 66;
const int Divs = 6;
void subdivide( char ar[], int low, int high, int level );


int main()
{
	char ruler[Len];
	int i;
	for ( i = 1; i < Len - 2; i++ )
		ruler[i] = ' ';
	ruler[Len - 1] = '\0';
	int max = Len - 2;
	int min = 0;
	ruler[min] = ruler[max] = '|';
	std::cout << ruler << std::endl;


	for ( i = 1; i <= Divs; i++ )
	{
		subdivide( ruler, min, max, i );
		std::cout << ruler << std::endl;
		for ( int j = 1; j < Len - 2; j++ )
			ruler[j] = ' '; // reset to blank ruler
	}
	

	return 0;
}

void subdivide( char ar[], int low, int high, int level )
{
	if ( level == 0 )
		return;
	int mid = ( high + low )/ 2;
	ar[mid] = '|';
	subdivide( ar, low, mid, level - 1 );
	subdivide( ar, mid, high, level - 1 );	
}

I know the basics of functions, arrays, pointers, etc. My current project is 2d pong, so these things don't need to be explained. However, I always skipped recursion because I could never wrap my head around it. Thanks for any help.

[chinchang]

You might consider reading here.

[sk1v3r]

Recursion is just a function calling itself to get a job done.
Uses :
Binary trees
AI brute-forcing (like tic-tac-toe)
general things where recursion is easiest method

EXAMPLE:
take this function

void countDown(int number)
{
    cout << number << " ";
    if(number > 0)
    {
        countDown(number - 1);
    }
}

So if the user enters four, this is pretty much just:

number = 4
output 4
    number = 3
    output 3
        number = 2
        output 2
            number = 1
            output 1
               number = 0
               0 is not more than 0 so return

Recursion is a bit like a loop

[sakshamkum]

see we use recursion when we want to do something that is repetitive but has to be done in many phases.
we use recursion when we want to first complete a part of the job, work for its subparts, return to the same part and complete it and return back. there are many simple examples for recursion but I want to take a better example to say this



consider a program to generate all possible permutations of a word:
a word may be of any length and you have to find all the possible distinct words that can be formed using the characters by their arrangement
a word is there ABC
and all the words formed using the arrangement of its letters are
ABC
ACB
BAC
BCA
CAB
CBA



notice that when we arrange the first character we repeat it till we have arranged all the other characters with it in different order of position of their occurance. we do it recursively as we can see it has to be done in phases and we have to return to the previous phase to change the character and arrange all the others including the previous character for the next set of words arranged. by the time we return to the caller, all the distinct words would have been printed. for distnct we check that the character we are going to add should not repeat in the current phase. it it is not repeated we add it and proceed and if it repeats we donot add it.

[keithgarry]

Thanks very much! All your replies helped a lot and I'll be working on it this weekend.