recursion

[Shadow]

I have an assignment in my comp sci class and I have to use recursive methods to solve it. Sadly, we haven't covered recursion in class, and it's due on Friday, and I have 4 other major projects on teh go at the same time, so I don't really have time to teach myself using the godawful course notes the professor has come up with. I wonder if anyone knows of a really concise tutorial I can go through, or a website with very clear examples and explanations of recursion that I can take a look at.

Thanks in advance :)

edit: almost forgot: Java

[bjornredtail]

A recursive function is one that calls itself. They are particularly suited to certain types of problems where you need to do operations on more than one 'branch', like dealing with trees. Also note that, mathematically,  there is no recursive function that could not be re-written with loops.

Really nothing special in terms of programming... Just call a function within itself. Figuring out your algorithm might be a bit trickery though.

[Shadow]

I know the basica idea, but it's still an odd way of thinking for me. What I need is a solid example of a few simple recursive methods so I can work through and see how they are implemented. I've found a couple online, such as fibonacci sequences and triangle numbers and such, but they are mostly from other university's course notes and tend to ask questions without giving answers, so it isn't much help.

[The Lady Shael]

Code Select Expand


public static int power(int n, int times)
{
   if(times == 0) return; // base case
   return n * power(n, times-1);
}

public static String hello(int times)
{
  if(times == 0) return;
  return "hello" + hello(times-1);
}

public static void main(String[] args)
{
   power(3,2); // returns 9
   power(1,9); // returns 1
   hello(1); // returns "hello"
   hello(4); // returns "hellohellohellohello"
}



I hope that's right, just wrote it out without looking anything up. Just remember recursion usually has a base case or you'll be stuck in an infinite loop.

[Shadow]

My programming assignemt at the moment is to make a minesweeper game. The method I want to do recursively is one to calculate the number if mines in the proximity of a given square and assign that matrix index the number.

Any ideas? It doesnt really lend itself to recursion, but I don't have a choice.

[windhound]

*cough*
http://www.cs.ucf.edu/~reinhard/classes/cop3503/lectures/Recursion01.pdf
Page 6, first result of googling

A slight disclaimer, I'm sure you're smart enough to combine your existing knowledge with working examples to make code that's entirely yours, but well...  35 people in my year got caught with code that was not theirs when I took java.  They've got a rather smart comparator.
Infact, my ECE 406 teacher said he caught people cheating -this year- and the class is mostly seniors.  So yeah...

[Shadow]

No need to be like that with your *coughing* windy, I looked myself first and was unable to find anything that was really applicable to the problem I have to solve. This really isn't a problem that lends itself to recursion at all.

Oh don't worry, they pounded that one into my head with a brick for the first month of term.

[windhound]

Eh.  Some people are morally opposed to viewing solutions.
I linked to a partial solution to your problem.  Page 8 gives java code with recursion for the clear function in minesweeper

Its not a full solution, but it is a framework.  I took three semesters of java, and while rusty, it made sense to me and seemed to apply to your problem.

It calls itself from within itself, which to my memory is the definition of recursion.  Its a really weird thing to do, but hey

[Shadow]

That's a funcction to clear any clear squares adjacent to the one you click, whih sadly is not covered int eh assignment. Most of the code is given, I have to write three methods: one to generate a matrix of booleans, true if a mine is there and false if not. Not hard, but getting around repeat numbers was annoying. The second method is to calculate the number of mines adjacent to the square you click, and generate a matrix of integers to reflect this. This one I haven't done yet, and I think it might be the easiest one to use recursion on, but I am not sure. The final method is to check if the player wins, which means they have either flagged all mines or clicked all non mined squares. More annoying than it sounds, but I think I have that one worked out too.

It's not a hard project to do iteratively, but the recursive part is what is going to kill me.

[Shadow]

get rid of that in case googling turns up and they think i plagiarized