I'm learning to hate recursion terribly, but I need to do it for this project.
The point of the project is to go from pointA to pointB using recursion in java. And print out all paths.
my input is
5
3 0
1 3
output should be about 10 paths in form of (col,row)
can I get a few pointers and maybe a little help?
private void pathFinder(int row, int col, int xB, int yB, int[][] array)
{
if(row==xB && col==yB)
{
System.out.println("("+row+","+col+") ");
}
if(canIGoNorth(row,xB)==true)
{
System.out.print("("+row+","+col+") ");
pathFinder(row-1,col,xB,yB,array);
System.out.print("("+row+","+col+") ");
}
if(canIGoEast(col,yB)==true)
{
System.out.print("("+row+","+col+") ");
pathFinder(row,col+1,xB,yB,array);
System.out.print("("+row+","+col+") ");
}
}
inb4 learn to code, everythings wrong, and java sucks.
Name:
Anonymous2010-02-08 22:45
I'm learning to hate recursion terribly
Wut. Don't be a fag. Recursion is a natural product of having functions.
Anyway, I have no idea what problem you're trying to solve, but I can tell you that you probably want to do nested if/else. You just enumerate (on a piece of paper) every case you need to test for, then arrange the nested conditionals (because your language sucks and doesn't have cond) to test for them in whatever order you see fit. The way you've done it, after going North you'll try to go East, creating a branching tree of function calls, while you're trying to produce a simple iteration.
Name:
Anonymous2010-02-08 23:00
The problem is simple.
you have input in a .dat file
5
3 0
1 3
were 5 is the size of a grid/array
3 0 is the first point
and 1 3 is the point that you want to find the paths to.
As of right now I am just trying to find and print all the paths from Point A to point B.
>>5
What standards? There's problems which can't be solved without recursion - you'll end up emulating the stack yourself. Stop living in a dream world where everything feats neatly and look at the real world where both the input and problem domain are complex.
The very first rule abolishes recursion of any kind, direct or indirect. The rules also abolish dynamic memory allocation, so no, you can't emulate the stack yourself. The whole idea is to be able to statically calculate and prove upper bounds on stack space, memory usage, and processor instructions required to complete an operation.
Give me an example of a problem which can't be solved without recursion.
>>7
Try computing the Ackermann function, or traversing a tree/graph. You'll just end up emulating a stack or in the case of a tree/graph, you could avoid having a stack by keeping a sort of "next" pointer which allows you to traverse it sequentially in one way, but that just moves the cost of recursion from runtime to alloc time.
Those rules are fine for embedded programming, things like not using dynamic memory allocation(fixed pool of objects/memory?) are stupid on large systems as you'd eat into other processes memory and use more than you need at the moment. GC and dynamic allocation are perfectly fine for code meant for large systems (like our PCs).
>>9 you could avoid having a stack by keeping a sort of "next" pointer which allows you to traverse it sequentially in one way, but that just moves the cost of recursion from runtime to alloc time.
Yes, exactly! That's the whole point of the safety-critical guidelines.
Note that they don't abolish memory allocation; just *dynamic* memory allocation, i.e. allocation after program startup. That way a) you can give a formula for the program resource requirements based on its input, and b) if the program successfully starts, it can run indefinitely.
>>10
The point is to have statically calculable and provable resource requirements. Haven't you been paying attention?
Name:
Anonymous2010-02-09 0:41
The problem with your pathing is two: you're printing out jumbled directions and you can't go UP or LEFT. Instantiate this and give it a shot.
class PathFinder
{
protected int array[][];
public PathFinder(int d)
{
if(d <= 0)
{
throw new IllegalArgumentException("Parameter must be non-zero positive integer.");
}
this.array = new int[d][d];
for(int i = 0; i < d; i++)
{
Arrays.fill(this.array[i], 1);
}
}
>>5
Don't be an idiot. If you have functions, you have recursion; end of story. Natural product of having functions.
>>12
Stop continuing to be an idiot. Programs can't just reserve billions of gigabytes of memory on the off-chance that users will open that many files.
>>15
All "north east" paths meaning all paths that go up and to the right like 3,0 2,0 1,0 1,1 1,2 1,3
That is one path.
Name:
Anonymous2010-02-09 1:14
OK, so I was trying to not post my entire code just cause I know how terrible it is but here we go.
public class Recursion
{
public static void main(String[] args) throws FileNotFoundException
{
new Recursion();
}
public Recursion() throws FileNotFoundException
{
Scanner fileScan = new Scanner(new File("prog2.dat"));
int initSize = fileScan.nextInt();//holds the initial size.
int[][] mapGrid;
if(initSize>10)
{
System.out.println("The size is too large please enter new data.");
}
else
{
mapGrid = new int[initSize][initSize];//creates the array by the initial size.
//these two are the x,y coordinates of point A
int xPointA=getX(fileScan);
int yPointA=getY(fileScan);
//these two are the x,y coordinates of point B
int xPointB=getX(fileScan);
int yPointB=getY(fileScan);
if(canThisHappen(xPointA,yPointA,xPointB,yPointB)==false)
{
System.out.println("This can not happen because point B is below point A");
}
else
{
System.out.println("Paths:");
pathFinder(xPointA,yPointA,xPointB,yPointB,mapGrid);
}
}
}
//gets the x coordinate
private int getX(Scanner fileScan)
{
return fileScan.nextInt();
}
//gets the y coordinate
private int getY(Scanner fileScan)
{
return fileScan.nextInt();
}
//finds and prints the paths
private void pathFinder(int row, int col, int xB, int yB, int[][] array)
{
String output = "("+row+","+col+") ";
//tests to see if you are able to find NE routes
private boolean canThisHappen(int xA, int yA, int xB, int yB)
{
if(xA<xB || yA>yB || xB<0 || yB<0)
return false;
else
return true;
}
//test if you can go up.
private boolean canIGoNorth(int row, int xB)
{
if(row>xB)
return true;
else
return false;
}
//test if you can go right
private boolean canIGoEast(int col, int yB)
{
if(col<yB)
return true;
else
return false;
}
}
Maybe now you can understand what I am trying to do?
>>18
Please use the MASSIVE bb][code] FAILURE tag.
Name:
Anonymous2010-02-09 7:48
BB] MY ANUS
Name:
Anonymous2010-02-09 8:26
public class Recursion
{
public static void main(String[] args) throws FileNotFoundException
{
new Recursion();
}
public Recursion() throws FileNotFoundException
{
Scanner fileScan = new Scanner(new File("prog2.dat"));
int initSize = fileScan.nextInt();//holds the initial size.
int[][] mapGrid;
if(initSize>10)
{
System.out.println("The size is too large please enter new data.");
}
else
{
mapGrid = new int[initSize][initSize];//creates the array by the initial size.
//these two are the x,y coordinates of point A
int xPointA=getX(fileScan);
int yPointA=getY(fileScan);
//these two are the x,y coordinates of point B
int xPointB=getX(fileScan);
int yPointB=getY(fileScan);
if(canThisHappen(xPointA,yPointA,xPointB,yPointB)==false)
{
System.out.println("This can not happen because point B is below point A");
}
else
{
System.out.println("Paths:");
pathFinder(xPointA,yPointA,xPointB,yPointB,mapGrid);
}
}
}
//gets the x coordinate
private int getX(Scanner fileScan)
{
return fileScan.nextInt();
}
//gets the y coordinate
private int getY(Scanner fileScan)
{
return fileScan.nextInt();
}
//finds and prints the paths
private void pathFinder(int row, int col, int xB, int yB, int[][] array)
{
String output = "("+row+","+col+") ";
//tests to see if you are able to find NE routes
private boolean canThisHappen(int xA, int yA, int xB, int yB)
{
if(xA<xB || yA>yB || xB<0 || yB<0)
return false;
else
return true;
}
//test if you can go up.
private boolean canIGoNorth(int row, int xB)
{
if(row>xB)
return true;
else
return false;
}
//test if you can go right
private boolean canIGoEast(int col, int yB)
{
if(col<yB)
return true;
else
return false;
}
Name:
Anonymous2010-02-09 9:08
Recursion in a language that has no way to avoid stack overflow? Boy, education sure is taking leaps and bounds!
"Last year we stood before the abyss. This year, we are going to take a giant leap forward."
Name:
Anonymous2010-02-09 9:26
>>14 Programs can't just reserve billions of gigabytes of memory on the off-chance that users will open that many files.
Of course they don't. The idea is that they fail gracefully, operating within their resource limits.
Most naive implementations of the Ackermann function, as you posted, would crash horribly when attempting to compute it for large inputs; either failing to malloc() or just blowing out the stack. Even if it gracefully unwinds in error after a failed malloc(), it has still disturbed the operating system requesting a shitload of pages, and left fragmented memory if the computation is part of a larger program shared for other tasks.
An implementation without recursion or dynamic memory allocation would know its limits beforehand; requesting something outside that range would immediately result in a simple error message leaving the system intact. (The Ackermann function is probably not a good example since the values you can usefully compute are so small, but you get the idea.)
The point is, recursion is *not* a natural product of having functions. Thankfully, the software that guides missiles and lands planes does not use recursion.
>>23
Recursion is the natural product of having objects.
Name:
Anonymous2010-02-09 14:35
>>25 Recursion is the natural product of having functions.
Remember that recursive functions in C can be pretty useful too!
Name:
Anonymous2010-02-09 14:39
>>25
Recursion is the natural product of using functional programming instead of variable loops.
Name:
Anonymous2010-02-09 14:40
>>25
Recursion is the natural product of recursion.
Name:
Anonymous2010-02-09 14:45
Digital Counter(Iteration) vs Recursive Reference Construction(recursion)
The latter is more ``natural" or ``intuitive", though less suitable for computation.
Name:
Anonymous2010-02-09 15:07
>>27
All programming is recursive, if by recursive we mean, "Solve the simplest problem. Reduce complicated problems to simpler problems." Languages which force iterative constructs go against basic programming technique.
Name:
Anonymous2010-02-09 15:21
>>30
Thus, all programming shall be replaced by grunting and pointing at menus.
>>30
Stop being such a brainus, recursion means applying the same function to itself, either directly or indirectly, and hasn't anything to do with what the programmer is doing.
>>33
Put down your design patterns book and look at the forest bro.
Recursion in computer science
Main article: Recursion (computer science)
A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms.... Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself.
Recursion to iteration is what masturbation to sex.
Name:
Anonymous2010-02-09 17:24
>>23 as you posted
Wut wut? Losing IDs must have been ever so hard for you.
An implementation without recursion or dynamic memory allocation would know its limits beforehand; requesting something outside that range would immediately result in a simple error message leaving the system intact.
Brilliant! I'll just deliver an error message when users attempt to open files over 640kB in size, even though they have 8GB of memory.
The point is, recursion is *not* a natural product of having functions.
You're an idiot. Do you not know what “natural product” means? Tip: it's got nothing to do with whether something is a good idea or not.
Name:
Anonymous2010-02-09 19:26
>>39 Do you not know what “natural product” means? I do, and this knowledge confuses me.