4 Replies - 323 Views - Last Post: 08 April 2011 - 10:52 AM Rate Topic: -----

#1 keithgarry  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 63
  • Joined: 26-August 09

Understanding recursive calls

Posted 06 April 2011 - 08:49 AM

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



Posted Image

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Understanding recursive calls

#2 chinchang  Icon User is offline

  • Indie Game Developer
  • member icon

Reputation: 192
  • View blog
  • Posts: 725
  • Joined: 22-December 08

Re: Understanding recursive calls

Posted 06 April 2011 - 08:58 AM

You might consider reading here.
Was This Post Helpful? 1
  • +
  • -

#3 sk1v3r  Icon User is offline

  • D.I.C Addict

Reputation: 231
  • View blog
  • Posts: 668
  • Joined: 06-December 10

Re: Understanding recursive calls

Posted 06 April 2011 - 09:00 AM

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 :)
Was This Post Helpful? 2
  • +
  • -

#4 sakshamkum  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 19
  • View blog
  • Posts: 232
  • Joined: 09-June 09

Re: Understanding recursive calls

Posted 06 April 2011 - 10:50 AM

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.
Was This Post Helpful? 1
  • +
  • -

#5 keithgarry  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 63
  • Joined: 26-August 09

Re: Understanding recursive calls

Posted 08 April 2011 - 10:52 AM

Thanks very much! All your replies helped a lot and I'll be working on it this weekend.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1