Recursion solutions

Anyone got a good solution to avoiding recursion in projects that may have to run the same code at certain points in the function? For an example of what I mean, here is the function I'm trying to fix. The problem is, after having returned, it needs to continue checking the rest of the spaces around it. For now I'm using recursion, but there is a slight chance that it will run into a major ore vein and call itself too many times. (btw, what is that amount anyway? I could put in a simple anti-recursion counter :)/> ) I thought tables would help, making a sort of "recursion manager" where it simply inserts the code into the table ahead of where it is currently running, but I haven't been able to get it to work. Any sort of help is appreciated.

code

function check()
	if not ok then return end
	--check for lava
	turtle.select( 15 )
	if not turtle.detect() and turtle.place() then
		print( "[check]: Liquid detected!" )
		if turtle.refuel() then
			print( "[check]: Refueled using lava source!" )
			turtle.forward()
			check()
			turtle.back()
		else
			print( "[check]: Liquid was not lava!" )
			turtle.place()
		end
	end
	--check for ore
	if notwaste( turtle.compare ) then
		print( "[check]: Ore Detected!" )
		repeat turtle.dig() until turtle.forward()
		print( "[check]: Dug ore!" )
		check()
		turtle.back()
		ignoredFuel = ignoredFuel + 2
	end
	if not ok then return end
	turtle.turnLeft()
	--check for lava
	turtle.select( 15 )
	if not turtle.detect() and turtle.place() then
		print( "[check]: Liquid detected!" )
		if turtle.refuel() then
			print( "[check]: Refueled using lava source!" )
			turtle.forward()
			check()
			turtle.back()
		else
			print( "[check]: Liquid was not lava!" )
			turtle.place()
		end
	end
	--check for ore
	if notwaste( turtle.compare ) then
		print( "[check]: Ore Detected!" )
		repeat turtle.dig() until turtle.forward()
		print( "[check]: Dug ore!" )
		check()
		turtle.back()
		ignoredFuel = ignoredFuel + 2
	end
	turtle.turnRight()
	if not ok then return end
	turtle.turnRight()
	--check for lava
	turtle.select( 15 )
	if not turtle.detect() and turtle.place() then
		print( "[check]: Liquid detected!" )
		if turtle.refuel() then
			print( "[check]: Refueled using lava source!" )
			turtle.forward()
			check()
			turtle.back()
		else
			print( "[check]: Liquid was not lava!" )
			turtle.place()
		end
	end
	--check for ore
	if notwaste( turtle.compare ) then
		print( "[check]: Ore Detected!" )
		repeat turtle.dig() until turtle.forward()
		print( "[check]: Dug ore!" )
		check()
		turtle.back()
		ignoredFuel = ignoredFuel + 2
	end
	turtle.turnLeft()
	if not ok then return end
	--check for lava
	turtle.select( 15 )
	if not turtle.detectUp() and turtle.placeUp() then
		print( "[check]: Liquid detected!" )
		if turtle.refuel() then
			print( "[check]: Refueled using lava source!" )
			turtle.up()
			check()
			turtle.down()
		else
			print( "[check]: Liquid was not lava!" )
			turtle.placeUp()
		end
	end
	--check for ore
	if notwaste( turtle.compareUp ) then
		print( "[check]: Ore Detected!" )
		repeat turtle.digUp() until turtle.up()
		print( "[check]: Dug ore!" )
		check()
		turtle.down()
		ignoredFuel = ignoredFuel + 2
	end
	if not ok then return end
	--check for lava
	turtle.select( 15 )
	if not turtle.detectDown() and turtle.placeDown() then
		print( "[check]: Liquid detected!" )
		if turtle.refuel() then
			print( "[check]: Refueled using lava source!" )
			turtle.down()
			check()
			turtle.up()
		else
			print( "[check]: Liquid was not lava!" )
			turtle.placeDown()
		end
	end
	--check for ore
	if notwaste( turtle.compareDown ) then
		print( "[check]: Ore Detected!" )
		repeat turtle.digDown() until turtle.down()
		print( "[check]: Dug ore!" )
		check()
		turtle.up()
		ignoredFuel = ignoredFuel + 2
	end
end

You can use return to avoid the "recursion counter". I thought it was 256 max btw.

local function foo(stuff)
  --code
  return foo(more stuff)
end

Not really the best way, you should try to "derecurse" your function to a loop structure.

EDIT:
Check out this link: http://www.lua.org/pil/6.3.html

flaghacker, on 24 July 2014 - 10:34 PM said:

You can use return to avoid the "recursion counter". I thought it was 256 max btw.

local function foo(stuff)
  --code
  return foo(more stuff)
end

Not really the best way, you should try to "derecurse" your function to a loop structure.

The problem with that is, I don't want to return, I have code to run after the function is called again.

A simple (if lazy) solution I have used is to ignore ore veins and to mine in a pattern that checks every block which looks something like

CCDCCCCDC
DCCCCDCCC
CCCDCCCCD

Where D is a block that is dug out and C is a block that is checked (works pretty well with multiple turtles too) although you do lose some checks on the very edge rows and columns

When I have used recursive methods, it's been more for mining tree leaves to ensure I get a sapling to replant with where I normally cap it at 3, for mining I would say you would probably want to go higher. A pseudocode implementation would be something like this (sorry not at home so I can't just dump you my leaf trimmer script which would be pretty easy to modify)

directions={up="down", down="up",south="north",west="east",north="south",east="west"}
local function recursiveMine(RecurCount, ReturnDirection)
if RecurCount<6 then
	for side,antiside in pairs(direction) do
		if Block(side)=ore then
			 dig(side)
			 go(side)
			 recursiveMine(RecurCount+1,antiside)
		end
	end
end
go(ReturnDirection)
end

A while back someone made a tutorial for writing proper recursion. You can always use return statements, to end the funtion, but run a new function.

function foo()
  return foo()
end

hilburn, on 24 July 2014 - 10:38 PM said:

A simple solution (if lazy) solution I have used is to ignore ore veins and to mine in a pattern that checks every block which looks something like

CCDCCCCDC
DCCCCDCCC
CCCDCCCCD

Where D is a block that is dug out and C is a block that is checked (works pretty well with multiple turtles too) although you do lose some checks on the very edge rows and columns

When I have used recursive methods, it's been more for mining tree leaves to ensure I get a sapling to replant with where I normally cap it at 3, for mining I would say you would probably want to go higher. A pseudocode implementation would be something like this (sorry not at home so I can't just dump you my leaf trimmer script which would be pretty easy to modify)

directions={up="down", down="up",south="north",west="east",north="south",east="west"}
local function recursiveMine(RecurCount, ReturnDirection)
if RecurCount<6 then
	for side,antiside in pairs(direction) do
		if Block(side)=ore then
			 dig(side)
			 go(side)
			 recursiveMine(RecurCount+1,antiside)
		end
	end
end
go(ReturnDirection)
end

That code is not much different than what I'm using now. It'd be easier to simply do call each one with the variable recur, like this:

function recursiveFunc( nLevel )
 if nLevel > 250 then
   return
 end
 --#bla bla bla checking
 recursiveFunc( nLevel + 1 )
end

Cranium, on 24 July 2014 - 10:40 PM said:

A while back someone made a tutorial for writing proper recursion. You can always use return statements, to end the funtion, but run a new function.

function foo()
  return foo()
end

Yes, I know how to user "proper" recursion, but the way I need/want to use it does not allow for that unfortunately. Unless I returned the function, plus what I have left to do after and somehow ran that (lol variable stacking…)

So if I've got this right, the general gist of the function is that when the turtle encounters a vein of some sort, you want to use this function to recursively dig the whole thing out, and when the recursion is finished, the turtle should be located where it was when it started?

Lava lakes will kill that idea. They can get way too large for it. Your limit will be about a six-block-cubed area.

My general advice for recursion is this: There aren't that many applications that "require" it. No matter what the task, it probably isn't needed.

I guess if I were to try to take on this sort of task, I'd adapt this script I made for this "competition" (though unfortunately Konlab decided to butcher my code before running it, I can assure you it does work ;)/> ).

Ironically, it uses recursion, but not for the same task. The basic idea is that the turtle can explore an area, and keeps going until it either reaches a certain point or decides it's boxed it. If it reaches a dead end, it refers to a look-up table and paths back to the last location it knew wasn't a dead end.

The recursion (which likely isn't needed at all, I just felt like using it! :P/> ) comes in just for navigating between these pre-explored points (and even then it doesn't check all possible paths - it only needs to inspect well under 1% of them to find the best). Finding new points is handled by a "while" loop instead. I'm not sure how large an area it can handle, but rather I can only really sum it up as "huge".

So, yeah, I'd rig that to treat ores/lava/whatever as "open spaces" it's allowed to explore through, and everything else as impassable terrain. Once it decides it's boxed in I'd tell it to go back to its starting position.

I'm sure you'll want to use all of your own code, but looking at my pathfinder may at least give you some ideas.

Lava lakes don't register as "ore" as such when checking with turtles so can be handled differently quite easily. Also, with a 256 recursion stack limit it could quite happily suck up all the lava in a quarter kilometre radius without batting an eyelash, you'd hit the turtle fuel cap way before then

hilburn, on 25 July 2014 - 07:01 AM said:

Lava lakes don't register as "ore" as such when checking with turtles so can be handled differently quite easily. Also, with a 256 recursion stack limit it could quite happily suck up all the lava in a quarter kilometre radius without batting an eyelash, you'd hit the turtle fuel cap way before then

That's not true, you can suck up 256 blocks of lava total, not radius.

flaghacker, on 25 July 2014 - 07:11 AM said:

hilburn, on 25 July 2014 - 07:01 AM said:

Lava lakes don't register as "ore" as such when checking with turtles so can be handled differently quite easily. Also, with a 256 recursion stack limit it could quite happily suck up all the lava in a quarter kilometre radius without batting an eyelash, you'd hit the turtle fuel cap way before then

That's not true, you can suck up 256 blocks of lava total, not radius.

Nope, let's pretend we had the (rather unreasonable) situation of a turtle having run into a point where 4 250 block long lines of lava source blocks have converged, going N,E,W and Up. Turtle checks North, finds lava, sucks lava, goes North, stack depth 1 repeat until finally stack depth = 250. Turtle then goes back to where it started as there is no more lava, stack depth 0, then finds lava East… sucks up another 250 lava blocks, returns, West, Up etc, You have sucked up 1000 lava without exceeding a stack depth of 250.

Admittedly it's not actually a radius, but it's close enough, with a fixed stack limit of 250 blocks, the turtle doing something like this could suck up 3.83x10^7 as opposed to 6.54x10^7 blocks, but at that point the number is essentially arbitrarily large

Erm, that's not really a "radius" at all. Really what you're trying to say is that it's a matter of "how much lava would the turtle encounter before it needs to backtrack?".

The problem is that with the way the average lava lake forms, that figure is very likely to exceed the ~256 block limit. Yes, it's easy to envision set ups where the turtle would be forced to backtrack before hitting it and so could continue through massive areas, but those are very unlikely to actually be encountered in the field, I'm afraid.

Like I said, it's not actually a radius, if you want to be precise about it; the theoretical recursive range of a turtle is an octahedron of side length and height 513m. This is because of the way the function works, so long as there is contiguous lava, the turtle can access anything within 256 blocks of it's starting point through any combination of twists and turns, so while the distance travelled is limit 256, the number of blocks checked/mined is much much higher. The simplest example of this is recursive "depth" of 0, where the turtle doesn't move at all, but can check and mine 6 blocks. Obviously it is less than this in practice because of being bound by a world height of <256 (discounting bedrock) and that the majority of interesting stuff happens below sea level, so really the working height is only about 60.

Anyway my point originally was that lava would not "kill that idea", you may not get all of the lava in a single recursion but you would get a more than sufficient quantity for the purposes of refuelling the turtle and/or preventing the branch being flooded by lava. You can then get the rest of the lava many branches later when you come across the remnants of the lake. Recursion in branch mining turtles is a practical way of maximising ores/fuel, though just mining out a 3x1 strip as it discounts the need for turns, or as chunkloading then becomes an issue, mining out 3 high layers in a quarrylike manner (ignoring junk) is a much better return in terms of ore/hour.

Another response to Yami's original query, if you wanted to achieve this without recursion (though tbh I don't see an issue with using it) you could probably do it in a loop by appending the location to a table, checking for ores, digging out an ore if it exists and going there, or removing the last location from the table, going to the previous last location, checking, digging etc, when that table is length 0 you are back where you started, so you could loop with repeat … until #pos_table==0 or something

I've got a little better explanation as to how the recursion will work.

1) turtle mines until it has 200 recursion (that's what I set it as)
2) turtle recedes 1 level
3) turtle checks again, and will mine if it finds something
4) turtle has reached 200 again
5) turtle recedes 1 level
6) turtle recedes again, having completed it's check
7) turtle now has 2 recursion levels to mess with…
8) repeat

The table thing is a little more complicated than you think, I've been frustrated at every turn. I think I'm going to end up simply letting the turtle run out of recursion, because really with 200 block range, isn't it going to run out of inventory/fuel space?

Edit: Also the lava thing isn't working, it's identifying the block in front of it (air) as being lava because it picked up the lava below said air block. >:(/>

KingofGamesYami, on 25 July 2014 - 03:52 PM said:

Edit: Also the lava thing isn't working, it's identifying the block in front of it (air) as being lava because it picked up the lava below said air block. >:(/>

Meh, if it works under CC 1.5x, I'd say that's good enough. Dan'll fix the relevant bugs for 1.6x sooner or later.

Bomb Bloke, on 25 July 2014 - 05:38 PM said:

KingofGamesYami, on 25 July 2014 - 03:52 PM said:

Edit: Also the lava thing isn't working, it's identifying the block in front of it (air) as being lava because it picked up the lava below said air block. > :(/>

Meh, if it works under CC 1.5x, I'd say that's good enough. Dan'll fix the relevant bugs for 1.6x sooner or later.

Yeah, um, I fixed it now lol. All I needed to do was confirm it wasn't an air block (by comparing an empty slot)

So I had some free time and knocked up some code that I think should work using tables and a loop rather than recursion

Can't test it right now, but I'm 95% sure it shouldn't have any ridiculous bugs

http://pastebin.com/hzDcF1LR

Hope this helps