File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes Problem with recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Problem with recursion" Watch "Problem with recursion" New topic

Problem with recursion

mario tan

Joined: Mar 09, 2005
Posts: 10
Hi guys,

Ive read an article which talks about recursion and I find it very interesting. However my mind boggles everytime I read the code from this article:

Connect 4 recursion

Please take time to look at the code..

You can see there that each time the method best_move is called, there is always that declaration and instantiation of best_score.

best_score is an instance of MoveValue.

Since this is a recursive method, will each call to the method best_move have its own copy of best_score? That means that there could be plenty of MoveValue object that will reside on the heap having only one name which is best_score?

I've tested the code but the best_move always return a MoveValue object with score = 0 and col = 6.

Why is that so?.. Can someone please explain to me the code and how to correctly trace it? Thanks in advance.

Best regards,

fred rosenberger
lowercase baba

Joined: Oct 02, 2003
Posts: 11955

I didn't look at the code, but the answer is probably yes.

when a method is called, any method variables get created. it doesn't matter who calls the method, a new set get created.

so, if you have a method call itself, the top level will have a copy, the next level will have its own copy, and so on, all the way down.

technically, object on the heap do not have names. if your method has a "best_score" variable, you actually have two things. you have the object itself that lives on the heap, and the REFERENCE named "best_score". the reference lives on the stack, and knows where its best_score object lives. each new 'best_score' reference hides all the previous ones, and the current one points to the current object.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
I agree. Here's the link:
subject: Problem with recursion
It's not a secret anymore!