AHHH RECURSION!!!

[TheNoobie]

I'm just learning about recursion in my C++ book and man is it ever confusing, is it going to be 100% necessary for me to master this before moving on? I don't ever really see it in too many programs I've dinked around in so I'm guessing it's not used very often but I could be wrong. Took me about 15 minutes (and a little bit of cheating) just to write this simple recursion program...

#include <iostream>
using namespace std;

int MultiplyPower(int, int);

int main()
{
	int numOne, numTwo, finalResult;

	cout << "Enter a number: ";
	cin >> numOne;
	cout << "Multiply by what power: ";
	cin >> numTwo;

	finalResult = MultiplyPower(numOne, numTwo);

	cout << "Final result: " << finalResult << endl;

	return 0;
}

int MultiplyPower(int numOne, int numTwo)
{
	if (numTwo > 1)
		return ( numOne * MultiplyPower(numOne, numTwo - 1) );
	return numOne;
}

Any advice to teach myself this a little bit better if it's necessary? Anyone else out there hate recursion? lol

[Mathhead200]

I hate recursion when it doesn't work, it's hard to follow linearly.
I love it when it works though, it make thing look so simple!

Try using it for applications where it makes sense to use it. For instance, a directory structure (file system) has a tree structure. You have root directory(s) (on Windows "C:", on Unix "/", …, etc) and they have folders, and each folder has folders, and so on. So in pseudo-code:

//print all the files in this root directory, as well as all files in all of its folders
void printAllFiles(rootDir) {
	filesAndFolders[] = rootDir.getAllFilesAndFolders();
	foreach( filesAndFolders as fileOrFolder )
		if( fileOrFolder is FILE )
			print( fileOrFolder ); //print the file
		else if( fileOrFolder is FOLDER )
			printAllFiles( fileOrFolder ); //pass folder to another call to this function
				// so it prints all of it's files and folders too
}

[Disch]

is it going to be 100% necessary for me to master this before moving on?

No. I don't know why it's taught to beginners, it really shouldn't be.

I don't ever really see it in too many programs I've dinked around in so I'm guessing it's not used very often but I could be wrong

You're not wrong.

Practical uses for recursion are few and far between. About the only thing off hand I can think of where uses are warranted is something like navigating a tree or a flood fill algorithm.

[tition]

As one of my math teachers said, obviously any recursive algorithm can be converted to a non-recursive one (because that is exactly what your C++ compiler does).

So, recursion is not conceptually different from a while cycle and some pushing and popping of variables to and from a stack ;)

[ne555]

wikipedia wrote:

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

Does it matter how is it implemented?
Could we consider this code as a valid recursive example?

fibo = 1;
for(int K=2, fn_1=1, fn_2=1; K<=n; ++K){
  fibo = fn_1 + fn_2;  // Using the recurrence relation fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
  fn_1 = fn_2;
  fn_2 = fibo;
}

[Disch]

Could we consider this code as a valid recursive example?

No. That's just a loop. I suppose it might qualify as an iterative example.

Recursion [in most programming languages] has a very distinct meaning of a function/method calling a separate instance of itself.

[zeroelement]

Im also learning recursion. You might know more than me right now but if you think of it as a mirror refelcting a mirror it keeps going till the small angel (n) causes the mirrors to go to the side and stop. So its calling itself and once it finishes it prints from the inner most first out.

void f(char ch)
{
if ((‘A’ <= ch) && (ch <= ‘H’)) {
f(ch-1);
cout << ch;
} else
cout << endl;
}
1. f(‘C’)
2. f(‘G’)
3. f(‘3’)

1=(empty line) ABC is
2=(empty line) ABCDEFG
3= (empty line)