が、スタック処理を書けば擬似的に実現できます。
スタックには Array が必要ですが、FLASH Lite 1.1 には Array がありません。
普通は eval を使って擬似的に実装しますが、メモリを食うので再帰処理には不向き。
そこで String をスタックメモリに見立てて while します。

この再帰処理を Flash Lite 1.1 で書くとこんな感じ。

//mapを作る
mapSize	= 11;
mapData	= "";
moveData	= "";
moveRecData	= "";

for(i = 0; i < mapSize; i++ ) {
	for (j = 0; j < mapSize; j++ ) {
		mapData		= mapData add (1+random(3));
		moveData	= moveData add "1";
		moveRecData	= moveRecData add "0";
	}
}

unitX = 5
unitY = 5
unitMove = 4

//擬似再帰処理 --------------------------------

//PUSH
stack = ""
stack = stack add mbChr(unitX + 1) add mbChr(unitY - 1 + 1) add mbChr(unitMove + 1) add mbChr(1 + 1);//up
stack = stack add mbChr(unitX + 1 + 1) add mbChr(unitY + 1) add mbChr(unitMove + 1) add mbChr(2 + 1);//right
stack = stack add mbChr(unitX + 1) add mbChr(unitY + 1 + 1) add mbChr(unitMove + 1) add mbChr(3 + 1);//down
stack = stack add mbChr(unitX - 1 + 1) add mbChr(unitY + 1) add mbChr(unitMove + 1) add mbChr(4 + 1);//left

while(length(stack) > 3) {

	//SHIFT
	ax	= mbOrd(subString(stack, 1, 1)) - 1;
	ay	= mbOrd(subString(stack, 2, 1)) - 1;
	mv	= mbOrd(subString(stack, 3, 1)) - 1;
	di	= mbOrd(subString(stack, 4, 1)) - 1;
	stack	= subString(stack, 5);//この取り出し方だとスタックではなく正確にはキューというらしい。
	
	index = 1 + ax + ay * mapSize;
	if (subString(moveRecData, index,1) == 0) {
		switch(subString(mapData, index,1)) {
			case(1):	moveCost = 1;	break;
			case(2):	moveCost = 2;	break;
			case(3):	moveCost = 10;	break;
			default:	moveCost = 0;
		}
		if (mv - moveCost >= 0) {
			moveData = subString(moveData, 1, index-1 ) add "0" add subString(moveData,	index + 1);
			moveRecData = subString(moveRecData, 1, index-1 ) add "1" add subString(moveRecData,	index + 1);
			mv = mv - moveCost;
			//PUSH
			switch(false) {
				case(di == 3):stack = stack add mbChr(ax + 1) add mbChr(ay - 1 + 1) add mbChr(mv + 1) add mbChr(1 + 1);
				case(di == 4):stack = stack add mbChr(ax + 1 + 1) add mbChr(ay + 1) add mbChr(mv + 1) add mbChr(2 + 1);
				case(di == 1):stack = stack add mbChr(ax + 1) add mbChr(ay + 1 + 1) add mbChr(mv + 1) add mbChr(3 + 1);
				case(di == 2):stack = stack add mbChr(ax - 1 + 1) add mbChr(ay + 1) add mbChr(mv + 1) add mbChr(4 + 1);
			}
		}
	}
}

//実行結果 --------------------------------

trace("map ----------");
for(i = 0; i < mapSize; i++ ) {
	s = "";
	for (j = 0; j < mapSize; j++ ) {
		s = s add subString(mapData, 1 + j + i*mapSize,1) add " ";
	}
	t = "0000" add i;
	trace ( subString(t,length(t)-3) add " > " add s);
}
trace("move ----------");
for(i = 0; i < mapSize; i++ ) {
	s = "";
	for (j = 0; j < mapSize; j++ ) {
		s = s add subString(moveData, 1 + j + i*mapSize,1) add " ";
	}
	t = "0000" add i;
	trace ( subString(t,length(t)-3) add " > " add s);
}
trace("moveRec ----------");
for(i = 0; i < mapSize; i++ ) {
	s = "";
	for (j = 0; j < mapSize; j++ ) {
		s = s add subString(moveRecData, 1 + j + i*mapSize,1) add " ";
	}
	t = "0000" add i;
	trace ( subString(t,length(t)-3) add " > " add s);
}

※8/16追記
表題の再帰処理とは関係ないアルゴリズムの部分なんだけど、
上のソースでは検索する順序によって結果が違ってくるので
条件分岐はこう書いた方が冗長でもベターではなかろうかと思われる。

moveCostsByChip	= mbChr(1 + 1) add mbChr(2 + 1) add mbChr(10 + 1);

mapSize	= 11;
mapData	= "";
moveData	= "";
moveRecData	= "";

for(i = 0; i < mapSize; i++ ) {
	for (j = 0; j < mapSize; j++ ) {
		mapData		= mapData add (1+random(3));
		moveData	= moveData add "1";
		moveRecData	= moveRecData add "0";
	}
}

unitX		= 5;
unitY		= 5;
unitMove	= 4;

index		= 1 + unitX + unitY * mapSize;
moveCost	= mbOrd(subString(moveCostsByChip, subString(mapData, index, 1), 1)) - 1;
stack		= mbChr(unitX + 1) add mbChr(unitY + 1) add mbChr(unitMove + moveCost + 1) add mbChr(0 + 1);

while(length(stack) > 3) {
	ax	= mbOrd(subString(stack, 1, 1)) - 1;
	ay	= mbOrd(subString(stack, 2, 1)) - 1;
	mv	= mbOrd(subString(stack, 3, 1)) - 1;
	di	= mbOrd(subString(stack, 4, 1)) - 1;
	stack	= subString(stack, 5);
	
	index	= 1 + ax + ay * mapSize;
	mv	-= mbOrd(subString(moveCostsByChip, subString(mapData, index,1), 1)) - 1;
	
	if (mv >= 0) {
		moveData	= subString(moveData, 1, index - 1 ) add "0" add subString(moveData, index + 1);
		if (mv > subString(moveRecData, index, 1)) {
			moveRecData	= subString(moveRecData, 1, index - 1 ) add mv add subString(moveRecData, index + 1);
			switch(false) {
				case(di == 3):stack = stack add mbChr(ax + 1) add mbChr(ay - 1 + 1) add mbChr(mv + 1) add mbChr(1 + 1);
				case(di == 4):stack = stack add mbChr(ax + 1 + 1) add mbChr(ay + 1) add mbChr(mv + 1) add mbChr(2 + 1);
				case(di == 1):stack = stack add mbChr(ax + 1) add mbChr(ay + 1 + 1) add mbChr(mv + 1) add mbChr(3 + 1);
				case(di == 2):stack = stack add mbChr(ax - 1 + 1) add mbChr(ay + 1) add mbChr(mv + 1) add mbChr(4 + 1);
			}
		}
	}
}