Compile, "global variables" and recursion

Question

I am trying to do something similar to this, namely to make a Compile'd function outer that itself calls a Compile'd function inner which accesses a variable defined in outer. Copy-pasting the example Leonid gives in the link, I get no errors. However in my case, I want inner to be a recursive function.

So far I have tried (the functions are toy examples):

Clear[inner];
inner = Compile[ {{i, _Integer}, {j, _Integer}},
If[i >= j, Return[], AppendTo[bag, list]; inner[i + 1, j]];
,CompilationOptions -> {"InlineExternalDefinitions" -> True, 
"InlineCompiledFunctions" -> False} ]

and

Clear[outer];
outer = Compile[{{i, _Integer}},
Block[{list = Table[{0, 0}, {i}], bag},
bag = {list};
inner[1, i];
bag
]
, CompilationOptions -> {"InlineExternalDefinitions" -> True, 
"InlineCompiledFunctions" -> True}
]

Trying to execute this last piece results in the error message:

Compile::cret : The type of return values in (...) are different.
Evaluation will use the uncompiled function.

I have a hard time interpreting the output of CompilePrint in this case, so I cannot pinpoint the error in order to move further with this. Since I am able to create compiled recursive functions just fine in general, and the link provides a "hack" to make inner see the variables in outer, I think it should be possible to do this, but perhaps not...

EDIT: I have verified that the lingering MainEvaluate is not due AppendTo or some-such, by making the function inner even more basic. I have also tried all possible combinations of True/False for the CompilationOptions for both inner and outer with no success. So it seems to me that it's possible to compile either a recursive function, or a compiled function modifying a "global" variable when called from another compiled function, but not both =(

Answer 1

This seems to work. Use With to "inject" the inner definition into outer.

Clear[inner];
inner = Compile[{{i, _Integer}, {j, _Integer}},
   If[i >= j,
    0,
    AppendTo[bag, list];
    inner[i + 1, j]]];

Clear[outer];
outer = With[{inner = inner}, Compile[{{i, _Integer}},
    Block[{list = ConstantArray[0, {i, 2}], bag},
     bag = {list};
     inner[1, i];
     bag]]];

In[123]:= outer[5]

(* Out[123]= {{{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 
   0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 
   0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0,
    0}, {0, 0}, {0, 0}}} *)

There may of course be other variants that work e.g. using the inline capabilities of Compile. I did not have success going that route but maybe was doing something not quite right. And Compile can be grumpy at times. [Edit: but see full edit below.]

---

Edit

This version seems sleeker. Still unable to avoid external evaluation though.

Clear[inner];
inner[i_, j_] :=
 If[i >= j,
  0,
  AppendTo[bag, list];
  inner[i + 1, j]]
Clear[outer];
outer = Compile[{{i, _Integer}},
   Block[{list = ConstantArray[0, {i, 2}], bag},
    bag = {list};
    inner[1, i];
    bag],
   CompilationOptions -> {"InlineExternalDefinitions" -> True, 
     "InlineCompiledFunctions" -> True}];

In[163]:= outer[5]

(* Out[163]= {{{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 
   0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 
   0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0,
    0}, {0, 0}, {0, 0}}} *)

I think to make it fast one needs to use Internal`StuffBag or some such. I don't see AppendTo as being good for speed.