text:
Self-Interpreting Interpreter
Based on a comment by George Edison to this question, write the smallest self-interpreting interpreter.

You may use the language of your choosing.
Empty languages do not count.  Your program must be at least two characters long.
The program does not need to interpret the entire language, just a Turing-complete subset of language features (that contains the interpreter).
Quines don't count.
Do not use your language's built-in eval function or equivalent. Same goes for apply, etc.

(Hmm.. I should do something with /usr/bin/cat) what about Turing-completeness?

@ SHiNKiROU: Thanks, I didn't think of that as a test.  Updated.

Related: Language w/ the smallest interpreter written in itself on Stack Overflow, though are are few (only one?) answers that actually abide by the rules given here.

Do we have to rewrite that Scheme sexp parser, or can we consider the host language's ok?

@J B: The language's string processing utilities are fine, including the sexp parser.

See DBFI.  The page declares that it is "the shortest known Brainfuck self-interpreter and possibly the shortest self-interpreter amongst all imperative languages".

This could end up being very short if you assume the existence of something similar to eval but not quite the same, for example a function that reads in a string and converts it to program code.

@Michael Dickens: I think that's what my CI answer does.  I reluctantly omitted an operator that takes a character and converts it to its corresponding code fragment, but I did add support for defining and joining code fragments.

@HoaLongTam For my- oh, I mean, everyone's sake can you clarify whether a valid answer must use a Turing-complete language or not?

CI - 260
,(1p0(2d())(41(2d())('#((1p0()(10()(1d,1p$)=)<)$2d,1p$)(40(1d,1c$^)(''(1d,^)('0
'9('0-(,'0'9('0-2p10*+1p$)(!1d)~)$^)(0($)'$(^)'^(&)'&(c)'c(p)'p(d)'d(=)'=(<)'<(
>)'>(~)'~(.)'.(,)',(!)'!(+)'+(-)'-(*)'*(/)'/(%)'%()38p(1p3p0(3d)((2)(3)=p1d1p$)
=)$)~)=)=,2p$&)=)=)<)$$

320 → 260: Push simple character-to-instruction mappings, then fold over them.  This halves the code size per case (there are 18 cases), but costs 30 characters to do the folding.
This is another one of my constructed languages, (base interpreter hosted on Gist).  It's unique in that the language reifies code fragments.  That is, strings of instructions in this stack-based language are used to the same effect as data structures or closures in other languages:
1^      # Push a 1, and "lift" it to be a code literal.
(5 +)   # Define a code literal.
&       # Join the two code literals, forming (1 5 +)
$       # Execute the code literal.

The interpreter builds a code fragment of the entire program before running it, so it can also be considered a compiler.  Because of this, stacking the interpreter does not result in exponential run-time overhead.
The interpreter derives all of its operators directly from the host interpreter.  However, it does the parsing by itself, so the majority of the code is just sequences that translate characters into their respective code literals.  This isn't the same as using eval, but it reveals how dependent any programming language implementation is on the semantics of its host language/architecture.

Language reference:
Get the interpreter here
Blocks

( ... )
Create a "block", which is effectively a list of instructions
with no context.  Internally, it could even be machine code.
block $
Call a block.  The callee is handed the global stack, which
includes the block being called.
value ^
Lift a value.  Namely, turn it into a block that pushes that value.
Example:
   1 ^
== (1)

block1 block2 &
Join two blocks, forming one that runs both in sequence.
Example:
   (1) (2) &
== (1 2)

Stack manipulation

n c
Copy the nth value of the stack.
Example:
   5 4 3 2 1 0 3c
== 5 4 3 2 1 0 3

n p
Pluck the nth value of the stack (remove it, and bring it to front).
Example:
   5 4 3 2 1 0 3p
== 5 4 2 1 0 3

n d
Drop n values from the stack.  0d is a no-op.
Example:
   5 4 3 2 1 0 3d
== 5 4 3

Relational operators

a b (on_true) (on_false) =
Test if a equals b.  Consume all but the first argument, and call
on_true or on_false.  If one argument is zero and the other is any
other type, the result will be false.  Otherwise, a and b must be integers.
Example:
   3 3 ('0+ .) (1d) =
== 3 '0+ .

a b (on_true) (on_false) <
Test if a is less than b.  a and b must be integers.
Example:
   3 5 (1d 5) () <
== 3 1d 5
== 5

a b (on_true) (on_false) >
Test if a is greater than b.  a and b must be integers.
Example:
   3 5 (1d 5) () >
== 3

a lo hi (on_true) (on_false) ~
Test if lo <= a <= hi.  a, lo, and hi must be integers.
Example:
   3 0 10 ('0+ .) (1d) ~
== 3 '0+ .

I/O

c .
Put the character c (consuming it from the stack).
,
Get a character and push it to the stack.  If the end of file
has been reached, -1 is pushed.
c !
Unget a character.  Just like ungetc in C, only one pushback is allowed.

Integer literals

'c
Push the character c.
[0-9]+
Push a decimal integer.

Arithmetic

a b +
a b -
a b *
Add/subtract/multiply two numbers.
Example:
   3 5 + 7 3 + *
== 80

a b /
a b %
Division and modulus.  Unlike in C, these round toward negative infinity.

Miscellaneous

code # comment
The # character comments out everything to the end of the line.
)
Used to end blocks.  Can be used to end the whole program, too.
All other characters are ignored.

Binary Lambda Calculus, 232 bits (29 bytes)
0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010
See
  http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding
for details

Why isn't this the accepted answer D: BLC is amazing!

Can you explain it at all?

Unfortunately, Wikipedia removed the Binary Lambda Calculus page. My http://tromp.github.io/cl/cl.html page links to a preserved copy and to a paper I wrote explaining the workings of the interpreter.

I can't take credit for this one, but I thought I would share this amazing one:
Brainf*** (423)
>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]

BlockScript - 535
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

BlockScript is a trivial spaghetti stack-based language I created specifically for this challenge.  The base interpreter is blockscript.c .
Sample program (prints the first 15 Fibonacci numbers):
{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

The interpreter reads both source code and program input from standard input, in that order.  This means that to run an interpreter within an interpreter within an interpreter, simply copy and paste:
# Level 1
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 2
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 3
{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

Like the movie Inception, you pretty much can't go any deeper than three levels.  It's not a matter of time, but space.  BlockScript leaks memory profusely, and this has to do with how the language itself is designed.

Language reference:
Get the interpreter here
In BlockScript, the "stack" is not an array that is overwritten by subsequent operations like you may be used to.  It is actually implemented as an immutable linked list, and a stack persists for the duration of the program.  Also, no operator (except @) removes values from the stack.  However, stack modifications only affect the block in which they occur.
Value selection

a through z
Fetch the 0-25th item from the stack, and push it to the stack.  a refers to the head, or most recently pushed item, of the stack.

A through Z
Fetch the 0-25th item of the current frame, and push it to the stack.

[
Open a "frame" to select items from the stack reference (see below) on the head of the stack.  [ doesn't require a matching ], but frames are lexically scoped.  In BlockScript, "scope" is determined by braces ({ ... }) that form blocks.  Thus, opening a frame inside of a block will have no effect on code outside of the block.

]
Close the current frame, returning to the previous frame (if any).

Blocks

{ ... }
Create a "block", and push it to the stack.  Inside a block, the stack will start at what it was before the block, except the stack of the caller will be pushed on top.  Stacks are persistent and immutable in BlockScript, so blocks are closures.  The idiom {[ means open a block, then open a frame to start selecting arguments (using A through Z).  The return value of a block is the head of the stack when } is reached.
Example:
 '3 '2 '1 {[ b. d. f. B. C. D. A! } 'D 'C 'B d!;

This prints 123BCD123DCB123BCD123DCB… .  The lowercase letters refer to stack values, while the uppercase letters refer to arguments (because the frame is set to the stack of the caller).  A! takes the head of the caller (which is guaranteed to be the block being called) and calls it.  If you're wondering why it reverses BCD every other time, it's because B. C. D. pushes those arguments in reverse order right before the block calls itself.

!
Call a block.  Push the return value to the stack.

Stack references

&
Create a stack reference, and push it to the stack.  Think of this as "super-cons", as it effectively takes every item on the stack and forms a "tuple" out of it.  The idiom &[ means that whatever a, b, c referred to before can now be accessed with A, B, C (for the remainder of the block or until ] is encountered).
In part because & captures more values than it usually needs, BlockScript leaks memory by design.

@
Switch to the stack pointed to by the stack reference a.  This operator is rather weird, but the BlockScript self-interpreter uses it a couple times to avoid having to push the same arguments twice.  The effects of @ (or any stack operation, for that matter) are confined to the block in which it is invoked.  Also, the frame is unaffected by @, so the frame can be used to grab values you need after switching stacks.

Conditional expression

? <on true> : <on false>
Conditional expression, just like the ternary operator in C.  That is, if a is "true" (that is, not equal to the integer zero), then do <on true>, otherwise do <on false>.

I/O
Note: Input and output are done in UTF-8.  A "character" is an integer corresponding to a Unicode index.

,
Get the next character of input, and push it to the stack.  If the end of input is reached, push -1 instead.

.
Output the character on the head of the stack.

Integer/character literals
Note: Integers and characters are the same thing in BlockScript.

'c
Push the character c.

[0-9]+
Push a decimal integer.

Arithmetic
These operators only work on integer values.

+ Compute b + a (pushing the result, but not discarding either value).
- Compute b - a.
* Compute b * a.
/ Compute b / a (integer division; rounds toward negative infinity).
% Compute b % a (integer modulus; rounds toward negative infinity).

Relational operators
These operators only work on integer values.

< If b is less than a, push 1, else push 0.
>
=

Miscellaneous

# Comment to end of line
The program must end with ;
All other characters are ignored.

Christ. Care to share the spec like you did for CI?

@Casey: Added a reference.

Would you be interested in knowing that you're dreaming? ...At level 4.

Zozotez LISP: 414
linefeeds added to get a nice block is not needed and not counted.
((\(E V A L)(E(r)'(())))(\(x e)(?(s x)(V x e)((\(b j)(?(= b ")(a j)(?(= b \)x
(?(= b ?)(?(E(a j)e)(E(a(d j))e)(E(a(d(d j)))e))(?(s b)(A b(E(a j)e)(E(a(d j)
)e))(E(a(d(d b)))(L(a(d b))j e)))))))(E(a x)e)(d x))))(\(x g)(? g(?(= x(a(a
g)))(d(a g))(V x(d g)))x))(\(f h v)(?(= f r)(r)(?(= f p)(p h)(?(= f s)(s h)(?
(= f a)(a h)(?(= f d)(d h)(?(= f =)(= h v)(c h v))))))))(\(k v i)(? k(L(d k)(
d v)(c(c(a k)(E(a v)i))i))i)))

In theory it should be able to run itself, but since the original interpreter is a BrainFuck binary and itself an interpreter I have only been able to test each part. When given itself and a simple expression (p p) I think it needs more time than the 40 minutes I have waited so far and I'm using my fast jitbf to run it which (mis)uses Perl Inline-C to run C code on the fly.
It's impossible to implement the whole Zozotez in Zozotez since it does not have means of mutating cons and : (setq/define) need that to update bindings. I also didn't implement explicit begin/progn or &rest argument, macros and special printing arguments since I didn't use it in the interpreter. I did include p (print) even though I don't use it so programs need to explicit print their calculations just like the original interpreter.
The same ungolfed:
;; A stand alone Zozotez script need to be
;; contained in one expression, here with
;; all functions provided as arguments to
;; get them bound in the dynamic environment
((\ (E V A L)
  (E(r)'(())))
 ;; E (EVAL)
 (\ (x e)
   (? (s x)
      (V x e)
      ((\ (b j)
         (? (= b ") (a j)
         (? (= b \) x
         (? (= b ?) (? (E(a j)e) (E(a(d j))e) (E(a(d(d j)))e))
         (? (s b)
            (A b (E(a j)e) (E (a(d j))e))
            (E (a(d(d b))) (L(a(d b))j e)))))))
       (E (a x) e)(d x))))
 ;; V (VALUE / symbol->value)
 (\ (x g)
   (? g
      (? (= x (a (a g)))
         (d (a g))
         (V x (d g)))
      x))
 ;; A (APPLY) but just for primitives
 (\ (f h v)
   (? (= f r) (r)
   (? (= f p) (p h)
   (? (= f s) (s h)
   (? (= f a) (a h)
   (? (= f d) (d h)
   (? (= f =)
      (= h v)
      (c h v))))))))
 ;; L ( joint evLis / extend-env)
 (\ (k v i)
   (? k
      (L (d k)
         (d v)
     (c (c (a k)
           (E (a v) i))
        i))
      i)))

GORBITSA, 493 bytes
S255 O253 R I188 B12 I68 o252 S1 O250 i252 S0 B2 S71 O255 S18 O254 S0 B134 B143 S79 O255 S25 O254 S0 B134 B149 S82 O255 S32 O254 S0 B134 B155 S66 O255 S39 O254 S0 B134 B158 S73 O255 S46 O254 S0 B134 B168 S84 O255 S53 O254 S0 B134 B172 S83 O255 S60 O254 S0 B134 B175 S65 O255 S67 O254 S0 B134 B179 S103 O255 S74 O254 S0 B134 B185 S111 O255 S81 O254 S0 B134 B193 S114 O255 S88 O254 S0 B134 B201 S98 O255 S95 O254 S0 B134 B207 S105 O255 S102 O254 S0 B134 B219 S116 O255 S109 O254 S0 B134 B224 S115 O255 S116 O254 S0 B134 B230 S97 O255 S123 O254 S0 B134 B239 G251 s253 I1 A252 B255 S2 i251 i250 S0 B12 g251 s253 I1 A255 b254 S1 i254 S0 b254 g250 O248 g248 O249 S0 B124 g250 O248 G249 o248 S0 B124 r249 S0 B124 G249 B162 S0 B124 g250 O251 I1 O250 S0 B12 g250 i249 S0 B124 t249 S0 B124 g250 O249 S0 B124 g250 O248 g248 i249 S0 B124 g250 O248 g248 O248 g248 O249 S0 B124 g250 O248 g248 O248 G249 o248 S0 B124 g250 O248 R o248 S0 B124 G249 B211 S0 B124 g250 O248 g248 O251 I1 O250 S0 B12 g250 A249 o250 S0 B124 g250 O248 g248 T S0 B124 g250 O248 g248 O248 G249 s248 O249 S0 B124 g250 O248 g248 O248 G249 a248 O249 S0 B124

Since GORBITSA is kind of strange, I will specify that this runs in ROM mode, while the code it interprets is in RAM mode. Explaining this is kind of weird, but I'll do my best. The 256 command limit on ROM mode killed me for a while.
Explained
(Full pseudocode I translated this to AFTER I wrote this (yeah, I wrote this with no extra utilities) can be found here).
Header:
S255 O253 R I188 B12 I68 o252 S1 O250 i252 S0 B2

Essentially, this part takes the input. It reads STDIN and stores it in the next free spot in memory (starting at 0). If the input is char code 68 ("D"), it will branch to the letter parsing script. Otherwise, it branches back to the beginning of the header and takes another bit of STDIN.
Letters:
S71 O255 S18 O254 S0 B134 B143
S79 O255 S25 O254 S0 B134 B149
S82 O255 S32 O254 S0 B134 B155
S66 O255 S39 O254 S0 B134 B158
S73 O255 S46 O254 S0 B134 B168
S84 O255 S53 O254 S0 B134 B172
S83 O255 S60 O254 S0 B134 B175
S65 O255 S67 O254 S0 B134 B179
S103 O255 S74 O254 S0 B134 B185
S111 O255 S81 O254 S0 B134 B193
S114 O255 S88 O254 S0 B134 B201
S98 O255 S95 O254 S0 B134 B207
S105 O255 S102 O254 S0 B134 B219
S116 O255 S109 O254 S0 B134 B224
S115 O255 S116 O254 S0 B134 B230

This section is rather self-explanatory. For each letter, you increment by an amount and then branch to subtraction. If it is 0 (i.e. the current letter is whatever the line is checking) it will then branch to the letter's parsing. Otherwise, it jumps to the next letter. When all letters are done being checked, it jumps to Potential Exit
Potential Exit
S97 O255 S123 O254 S0 B134 B239 G251 s253 I1 A252 B255 S2 i251 i250 S0 B12

This section checks to see if there are no letters left to execute. If there are, it increments the pointers so they reference the next character + its argument, and then jump to the beginning of Letters. Otherwise, it terminates by branching to a null instruction.
Subtraction
g251 s253 I1 A255 b254 S1 i254 S0 b254

Very simple. Uses XOR subtraction to check if the current character is equal to a character stored in another part of memory (set by the letters section).
Letter Evaluation
g250 O248 g248 O249 S0 B124
g250 O248 G249 o248 S0 B124
r249 S0 B124 G249 B162 S0 B124
g250 O251 I1 O250 S0 B12 g250 i249 S0 B124 t249 S0 B124
g250 O249 S0 B124
g250 O248 g248 i249 S0 B124
g250 O248 g248 O248 g248 O249 S0 B124
g250 O248 g248 O248 G249 o248 S0 B124
g250 O248 R o248 S0 B124 G249 B211 S0 B124
g250 O248 g248 O251 I1 O250 S0 B12 g250 A249 o250 S0 B124
g250 O248 g248 T S0 B124
g250 O248 g248 O248 G249 s248 O249 S0 B124
g250 O248 g248 O248 G249 a248 O249 S0 B124

Each line corresponds to the same line in the Letters section. These simply interpret each character (G O R B I T S A g o r b i t s a) in descending order and then branch to Potential Exit.

Concurrent Filesystem Befunge 98 - 53\18 bytes (almost certainly cheating)
Full 53 byte interpreter with no restrictions (although I haven't tested complicated timing interactions involving IP splitting and wrapping):
v ;;;;;;;;
>]390'ai@
 t;;;;;;;;
;>zzzzz#;

Reads input from a file named a and executes it. It isn't specifed in the rules that we can't use self-modifying code.
18 byte interpreter that does not allow wrapping (the IP moving of one edge of the code and starting at the opposite edge):
]210'ai@
t
><

CHIQRSX9+ , 2 bytes
+I

There's no way to write a self-interpreting interpreter in this HQ9+-based language without using I, which runs a built-in interpreter that processes STDIN.

Nowhere in the rules does it say that built-in self interpreters are disallowed. It says for eval, which is for expressions, not programs.

How does one compute primes in this language?

@ppperry X is supposed to make the language Turing-complete (thus able to compute primes) in an implementation-dependent manner.

Acording to the Esolang page, the Perl interpreter's X command randomly perturbs the program and the executes it, meaning that one cannot use than command to deterministically compute primes. Can you give me of an example interpreter that lets you use X in the way you specified?

@ppperry Apparently the interpreter written in Perl is the only interpreter, so no. Also, what if there's a program that computes primes when "randomized" with a specific value?

The Perl interpreter does not provide any method of customizing the seed ti the RNG, so any such program would only work 1\256 of the time.


text:
Robot Finds Kitten
The challenge
The shortest code by character count to help Robot find kitten in the fewest steps possible.
Golfers, this is a time of crisis - Kitten gone missing and it's Robot's job to find it! Robot needs to reach Kitten in the shortest path possible. However, there are a lot of obstacles in Robot's way, and he needs you to program a solution for him.
Robot used to have a program do it for him, but that program was lost and Robot have no backup :(.
Robot's runtime is not the best, and the least characters Robot has to read from the source code, the least time it will spend processing, and that means Kitten will be found faster!
Robot's memory contains a map of the location he is currently in with the top representing North, bottom representing South, right representing East and left representing West. Robot is always in a rectangular room of an unknown size surrounded by walls, represented by # in his radar map. Areas Robot can walk in are represented by a space .
Robot's radar also scans for many obstacles in the room and marks them in various ASCII letters. Robot cannot walk across those obstacles. The radar will mark Kitten as the special ASCII character K, while Robot's location is marked with R.
Robot's navigation system works this way: He can understand a duo of direction and number of movement units he should travel to - for example, N 3 means 'go north 3 movement units'. Robot's radar map is made such that a movement unit is one ASCII character. Robot can only go in 4 directions and cannot travel diagonally.
Your task, brave Kitten saver, is to read Robot's radar map once, and output the least amount of directions, with the least movement unit travel distance. Robot is guaranteed to have at least one path to Kitten.
To ensure Robot does not waste time executing a malfunctioning program that will not help Robot find Kitten, I encourage you, brave Kitten saver, to use this output of Robot's past program to ensure no time is wasted on finding Kitten!
Test cases
Input:
    ######################
    #  d      3    Kj    #
    #                    #
    # R                  #
    #      q             #
    ######################
Output:
    E 13
    N 2

Input:
    ######################
    #  d  r   3    Kj    #
    #    p        p      #
    #         T        X #
    #      q   s   t     #
    #                    #
    #  R o    d     W    #
    #                    #
    #    g      t     U  #
    #                    #
    ######################
Output:
    N 1
    E 10
    N 4
    E 2

Input:
    ######################
    #  spdfmsdlwe9mw WEK3#
    #    we    hi        #
    #   rdf         fsszr#
    #     sdfg  gjkti    #
    #   fc  d g i        #
    #     dfg    sdd     #
    #    g        zfg    #
    #  df   df           #
    #             xcf   R#
    ######################
Output:
    N 1
    W 9
    N 5
    E 4
    N 1
    E 4
    N 1

Code count includes input/output (i.e full program).

Possibly inspired by this game? http://www.kongregate.com/games/Hamumu/robot-wants-kitty

Nope, http://www.robotfindskitten.org/

The goal isn't unambigious. "output the least amount of directions, with the least movement unit travel distance." There might be a way with n directions and m steps and another one with less than n directions but more steps, or more directions and less steps. Is there an exchange rate?

Number of steps is better than number of direction.

If the idea is having the least number of steps, and break ties by the least number of directions, then the second example has a wrong solution. See my answer for a shortest path.

Thank you Daniel, my example is fixed - I guess my demo app wasn't perfect :(

See my slightly less than perfect solution for a simple map that will detect distance non-optimization for some solvers. Mine included. A fine job of setting the challenge, as usual.

@LiraNuna I came back from your link, my eyes hurts because the black-white contrasting :/

Is there a limit on the size of the radar map? I'd like to hard-code an arry in my C solution.

@FUZxxl: "Robot is always in a rectangular room of an unknown size surrounded by walls", however people have "cheated" and got up to 99x99 grids in the past. That is not a concern, as golfers normally "cheat" to gain better number of strokes.

C++ 1002 899 799chars
Note requires the use of C++0x to eliminate the space between > > in templates.
It does find the route with the minimum number of turns.
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<memory>
#define D make_pair
#define F first
#define S second
using namespace std;typedef pair<int,int>L;typedef vector<L>R;typedef multiset<pair<float,pair<L,R>>>B;vector<string> M;string l;int z,c,r=0;set<L> s;B b;L n;B::iterator f;R v;void A(int x,int y,int w){n=f->S.F;for(c=1;(z=M[n.S+=y][n.F+=x])==32||(z==75);++c)v.back()=D(w,c),b.insert(D(f->F+c+1./c,D(n,v)));}int main(){for(;getline(cin,l);++r){if((c=l.find(82))!=string::npos)b.insert(D(0,D(D(c,r),R())));M.push_back(l);}while(!b.empty()){f=b.begin();n=f->S.F;v=f->S.S;if(M[n.S][n.F]==75)break;if(s.find(n)==s.end()){s.insert(n);v.push_back(L());A(0,1,83);A(0,-1,78);A(1,0,69);A(-1,0,87);}b.erase(f);}for(c=v.size(),r=0;r<c;++r)n=v[r],printf("%c %d\n",n.F,n.S);}

It Dijkstra's Algorithm for solving the shortest path problem.
To distinguish between multiple equal size routes a long straight line has less weight that multiple short lines (this favors routes with less turns).
Cost of a path:  Len + 1/Len

Looking at Test Case 1:
========================
Thus Path E13 + N2 has a cost of
      13 + 1/13 + 2 + 1/2
An alternative path E9 + N2 + E4 has a cost of
      9 + 1/9 + 2 + 1/2 + 4 + 1/4

The difference is
      Straight Path:   1/13 <   Bendy Path: (1/9 + 1/4)

In a more readable form:
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<memory>

using namespace std;
typedef pair<int,int>                   L;
typedef vector<L>                       R;
typedef multiset<pair<float,pair<L,R>>> B;
vector<string>                          M;

string      l;
int         z,c,r=0;
set<L>      s;
B           b;
L           n;
B::iterator f;
R           v;

void A(int x,int y,int w)
{
    n=f->second.first;
    for(c=1;(z=M[n.second+=y][n.first+=x])==32||(z==75);++c)
        v.back()=make_pair(w,c),
        b.insert(make_pair(f->first+c+1./c,make_pair(n,v)));
}

int main()
{
    for(;getline(cin,l);++r)
    {
        if((c=l.find(82))!=string::npos)
            b.insert(make_pair(0,make_pair(make_pair(c,r),R())));
        M.push_back(l);
    }

    while(!b.empty())
    {
        f=b.begin();
        n=f->second.first;
        v=f->second.second;

        if(M[n.second][n.first]==75)
            break;

        if(s.find(n)==s.end())
        {
            s.insert(n);
            v.push_back(L());
            A(0,1,83);
            A(0,-1,78);
            A(1,0,69);
            A(-1,0,87);
        }
        b.erase(f);
    }

    for(c=v.size(),r=0;r<c;++r)
        n=v[r],
        printf("%c %d\n",n.first,n.second);
}

Scala 2.8 (451 characters)
...but it doesn't solve ties in favor of least amount of directions (though it does find the least amount of steps).
val m=io.Source.stdin.getLines.map(_.toArray).toSeq
var l=m.indexWhere(_ contains'R')
var c=m(l)indexOf'R'
val q=collection.mutable.Queue(l->c->"")
def s{val((l,c),p)=q.dequeue
if("R "contains m(l)(c))for((i,j,k)<-Seq((-1,0,"N"),(0,1,"E"),(1,0,"S"),(0,-1,"W")))q.enqueue(((l+i,c+j),p+k))
m(l)(c)='X'}
def P(s:String){if(s.nonEmpty){val (h,t)=s.span(s.head==)
println(s.head+" "+h.size)
P(t)}}
def Q{s
val((l,c),p)=q.head
if (m(l)(c)=='K')P(p)else Q}
Q

Scala 2.8, 642 characters, solves ties correctly;
val m=io.Source.stdin.getLines.toSeq
var b=Map(0->0->0).withDefault(_=>Int.MaxValue)
var l=m.indexWhere(_ contains'R')
var c=m(l)indexOf'R'
val q=collection.mutable.PriorityQueue(l->c->List((' ',0)))(Ordering.by(t=>(-t._2.map(_._2).sum,-t._2.size)))
def s{val(p@(l,c),u@(h@(d,n))::t)=q.dequeue
if("R ".contains(m(l)(c))&&u.map(_._2).sum<=b(p)){b=b.updated(p,u.map(_._2).sum)
for((i,j,k)<-Seq((-1,0,'N'),(0,1,'E'),(1,0,'S'),(0,-1,'W'))){
val o=if(k==d)(d,n+1)::t else (k,1)::h::t
q.enqueue(((l+i,c+j),o))}}}
def P(l:List[(Char,Int)]){l.reverse.tail.foreach{t=>println(t._1+" "+t._2)}}
def Q{s;val((l,c),p)=q.head;if (m(l)(c)=='K')P(p)else Q}
Q

It discovered a shorter path for the second example than the one given in the problem:
N 1
E 10
N 4
E 2

Python 2.6 (504 characters)
import sys,itertools
W,Q=len,list
M=[]
B=[]
for l in sys.stdin.readlines():
    r=Q(l.strip())
    B.append([0]*W(r))
    M.append(r)
    if "R" in r:x,y=r.index("R"),W(B)-1
def S(B,M,x,y,P):
    c=M[y][x]
    b=B[y][x]
    if b and W(P)>b:return 0
    B[y][x]=W(P)
    if c=="K":return P
    elif c=="R" and P:return 0
    if c in "R ":
        b=[]
        for q,w,s in((1,0,"E"),(-1,0,"W"),(0,-1,"N"),(0,1,"S")):
            r=S(B,M,x+q,y+w,P+s)
            if r and(W(r)<W(b)or not b):b=r
        if b:return b
    return 0
print "\n".join(k+str(W(Q(g)))for k,g in itertools.groupby(S(B,M,x,y,"")))

This doesn't seem to solve ties in favor of least steps.

Python 2.6 (535 characters)
exec 'eJzNlLFugzAQhneewhki2/KBworksVOkDu3QgVqVE2hBioFgCDhV371nJ1VbKR3SKYtl/jvs77MwtenafiBVqbs9WGcjLW05MB69tj05QEfqhpTNaMpeDyXDhsQORd3wLCK+YwT7u6PzFVK/Ep9Tsn6gmU50UTA2woHzc01KuqYZ20PPZSh85/iCO2etzBnTG8tcvlLxnovTPFVxzyGEC4lpiBay5xiuYMXBcRVtzxqTfP+IpqrelaRFsheoYJbBNvFj13asxd23gXHGmZU7bTaFDgiZH+MUYydtKBuZRuS0nvPmOt564Sl3CmlxcWAG6D3lXIkpeUMGB7nyfj82HW3FWvjTTVSYCXNJEUupEimannu+nl04WyM8XoB1F13E9S6Pt+ki0vDZXOdyd5su8X9cnm7DBa/tLGW4yh7yKCn1rIF+9vSTj/HiBeqCS1M3bMrnwOvbl5Ysi+eGLlkBhosjxl1fNwM5Ak7xH6CiT3SdT4U='.decode('base64').decode('zlib')

Unpacks to a severely mistreated A* implementation. Reads stdin. Searches for solutions with minimal total distance. Breaks ties by preferring minimal number of directions. Lists moves to stdout. Finds kittens.
Unpacked:
The source has been manually anti-golfed in a few places in order to obtain a smaller compressed representation. For example, a for loop over the compass directions was unrolled.
import heapq,sys
a=set()
for v,p in enumerate(sys.stdin):
 for u,s in enumerate(p):
  if s in' KR':a.add((u,v))
  if s=='K':(q,r)=(u,v)
  if s=='R':y=(u,v)
o=[((abs(y[0]-q)+abs(y[1]-r),(y[0]!=q)+(y[1]!=r)),(0,0),y)]
c=set()
w={}
while o:
 _,h,x=heapq.heappop(o)
 c.add(x)
 s=lambda(u,v):(u,v-1)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'N'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 s=lambda(u,v):(u,v+1)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'S'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 s=lambda(u,v):(u+1,v)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'E'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 s=lambda(u,v):(u-1,v)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'W'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 if x==(q,r):
  z=''
  while x in w:
   _,x,(m,d)=min(w[x])
   z='%s %d\n'%(d,m)+z
  print z,
  o=[]

Ruby - 539 characters
Could do with a lot of improvement, but it does work for shortest steps as well as directions.
M=[*$<]
r=M.map{|q|q.index('R')||0}
k=M.map{|q|q.index('K')||0}
D=M.map{|q|q.split('').map{[99,[]]}}
def c h
h.map{|i|i.inject([[]]){|a,b|a.last[0]!=b ? a<<[b, 1]:a.last[1]+=1;a}}.sort_by{|a|a.length}[0]
end
def t x,y,s,i
z,w=D[x][y][0],D[x][y][1]
if [' ','R','K'].index(M[x][y, 1])&&(z>s||z==s&&c(w).length>=c([i]).length)
D[x][y]=[s,z==s ? w<<i:[i]]
s+=1
t x+1,y,s,i+['S']
t x-1,y,s,i+['N']
t x,y+1,s,i+['E']
t x,y-1,s,i+['W']
end
end
t r.index(r.max), r.max, 0, []
puts c(D[k.index(k.max)][k.max][1]).map{|a|a*''}

c++ -- 681 necessary characters
#include <string>
#include <iostream>
#include <sstream>
using namespace std;
int d[]={-1,0,1,0},i,j,k,l,L=0,p=41,S;string I,m,D("ESWN");
int r(int o,int s){S=s;while((m[o]==32||m[o]==37)&&m[o+S]-35)
if(m[o+S]-p)S+=s;else return o+S;return 0;}
void w(int o){for(i=0;i<m.length();++i)for(j=0;j<4;++j)
if(k=r(o,d[j])){stringstream O;O<<D[j]<<" "<<int((k-o)/d[j])<<"\n"<<I;
I=O.str();if(p-41)--p,m[k]=37,w(k);cout<<I;exit(0);}}
int main(){while(getline(cin,I))m+=I,l=I.length();
d[1]-=d[3]=l;I="";for(i=0;i<m.length();++i)
switch(m[i]){case 82:case 75:m[i]/=2;case 32:break;default:m[i]=35;}
do{for(i=0;i<m.length();++i)if(r(i,-1)+r(i,-l)+r(i,1)+r(i,l))
{if(m[i]==37)w(i);m[i]=p+1;}}while(++p);}

It first replaces all the obstacles on the map with into #s (and changes the values of K and R, to leave headroom in the character space for very long paths. Then it scribbles on the map. An iterative process marks all the successively accessible squares until it is able to reach the kitten in one move. After that is uses the same accessibility checking routine to find a string of positions that lead back to the start in minimal instructions. These instructions are loaded into a string by pre-pending, so that they print in the proper order.
I don't intend to golf it further as it does not properly resolve ties and can not be easily adapted to do so.
It fails on
#####
#   #
# # #
#R#K#
#   #
#####

producing
 $ ./a.out < kitten_4.txt
N 2
E 2
S 2

More or less readable version:
#include <string>
#include <iostream>
#include <sstream>
using namespace std;

int d[]={-1,0,1,0}
  , i, j, k
  , l      /* length of a line on input */
  , L=0    /* length of the whole map */
  , p=41   /* previous count  ( starts 'R'/2 ) */
  , S      /* step accumulator for step function */
  ;
string I/*nput line, later the instructions*/
  , m/*ap*/
  , D("ESWN"); /* Reversed sence for back tracking the path */

int r/*eachable?*/(int o/*ffset*/, int s/*step*/){
//   cerr << "\tReachable?"
//        << endl
//        << "\t\tOffset: " << o << " (" << o/5 << ", " << o%5 << ")"
//        << "  [" << m[o] << "]" << endl
//        << "\t\tStep: " << s
//        << endl
//        << "\t\tSeeking: " << "[" << char(p) << "]"
//        << endl
//        << "\t\tWall:    " << "[" << char(35) << "]"
//        << endl;
  S=s;
  while ( ( (m[o]==32)      /* Current character is a space */
        || (m[o]==37) ) /* Current character is a kitten */
      && (m[o+S]-35) /* Target character is not a wall */
      )
    {
//     cerr << "\t\tTry: " << o+S << "(" << (o+S)/5 << ", " << (o+S)%5 << ")"
//   << "  [" << m[o+S] << "]" << endl;
    if (m[o+S]-p       /* Target character is not the previous count */
    ) {
//       cerr << "\t\twrong " << "  [" << m[o+S] << "] !!!" << endl;
      S+=s;
    }
    else  {             /* Target character *is* the previous count */
//       cerr << "\t\tFound " << "  [" << m[o+S] << "] !!!" << endl;
      return o+S;
    }
  /* while ends */
      }
  return 0;
}

void w/*on*/(int o/*ffset*/){
//   cerr << "\tWON" << endl
//        << "\t\tOffset: " << o << "(" << o/5 << ", " << o%5 << ")"
//        << "  [" << m[o] << "]"
//        << endl
//        << "\t\tSeeking: " << "[" << char(p) << "]"
//        << endl;
  for(i=0;i<m.length();++i) /* On all map squares */
    for(j=0;j<4;++j)
      if (k=r(o,d[j])) {
//  cerr << "found path segment..."
//       << (k-o)/d[j] << " in the " << d[j] << " direction." << endl;
    stringstream O;
    O << D[j]
      << " "
      << int((k-o)/d[j])
      << "\n"
      << I;
    I = O.str();
//  cerr << I << endl;
    /* test for final solution */
    if (p-41)
      --p,m[k]=37, w(k); /* recur for further steps */
    cout << I;
    exit(0);
      }
    /* inner for ends */
  /* outer for ends */
}

int main(){
  while(getline(cin,I))
    m+=I,l=I.length();
//   cerr << "Read the map: '" << m << "'." << endl;
  d[1]-=d[3]=l;I="";
//   cerr << "Direction array:    " << D << endl;
//   cerr << "Displacement array: " << d[0] << d[1] << d[2] << d[3] << endl;
//   cerr << "Line length: " << l << endl;
  /* Rewrite the map so that all obstacles are '#' and the start and
     goal are '%' and ')' respectively. Now I can do pathfinding *on*
     the map. */
  for(i=0;i<m.length();++i)
    switch (m[i]) {
    case 82:         /* ASCII 82 == 'R' (41 == ')'  ) */
    case 75:m[i]/=2; /* ASCII 75 == 'K' (37 == '%' ) */
    case ' ':break;
    default: m[i]=35; /* ASCII 35 == '#' */
    };
//   cerr << "Re-wrote the map: '" << m << "'." << endl;
  do { /* For each needed count */
//     cerr << "Starting to mark up for step count "
//   << p-41+1  << " '" << char(p) << "'" << endl;
    for(i=0;i<m.length();++i){ /* On all map squares */
//        cerr << "\tTrying position (" << i/l << ", " << i%l << ")"
//      << "  [" << m[i] << "]"
//      << endl;
      if ( r(i, -1) /* west  */ +
       r(i, -l) /* north */ +
       r(i,  1) /* east  */ +
       r(i,  l) /* south */
       ) {
//    cerr << "Got a hit on : '" << m << "'." << endl;
//    cerr << "\twith '" << char(m[i]) <<" at position " << i << endl;
//    cerr << "target is " << char(37) << endl;
    if(m[i]==37)
      w(i); /* jump into the win routine which never returns */
    m[i]=p+1;
//  cerr << "Marked on map: '" << m << "'." << endl;
      }
    }
  } while(++p);
}

Ruby - 648 characters
Another one that fails the least number of directions test as I can't think of any easy way to embed it in A*.
m=$<.read.gsub /[^RK\n ]/,'#'
l=m.index($/)+1
s=m.index'R'
g=m.index'K'
h=->y{(g%l-y%l).abs+(g/l-y/l).abs}
n=->y{[y+1,y-1,y+l,y-l].reject{|i|m[i]=='#'}}
a=o=[s]
d=Array.new(m.length,9e9)
c,k,f=[],[],[]
d[s]=0
f[s]=h[s]
r=->y,u{u<<y;(y=k[y])?redo:u}
(x=o.min_by{|y|f[y]}
x==g ? (a=r[x,[]].reverse;break):0
o-=[x];c<<x
n[x].map{|y|c&[y]!=[]?0:(t=d[x]+1
o&[y]==[]?(o<<y;b=true):b=t<d[y]
b ? (k[y]=x;d[y]=t;f[y]=t+h[y]):0)})until o==[]
k=a.inject([[],nil]){|k,u|(c=k[1]) ? (k[0]<<(c==u-1?'E':c==u+1?'W':c==u+l ? 'N':'S')) : 0;[k[0],u]}[0].inject(["","",0]){|k,v|k[1]==v ? k[2]+=1 : (k[0]+=k[1]+" #{k[2]}\n";k[1]=v;k[2]=1);k}
puts k[0][3,9e9]+k[1]+" #{k[2]}\n"

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/2.5/

sort: votes


text:
Tree traversal: Depth-first search
Write the shortest code that traverses a tree, depth-first.
Input
Any programmatical structure found in your language of choice: lists, tuples, queues etc.
Output
A list of "names" of the nodes in correct order as shown in Depth-first search article at Wikipedia.
Requirement:
A node should be able to contain an infinite number of child nodes.
Also, you're not required to actually print the result, just returning the correct result with the ability to use it in your program will do; I didn't really print mine below in my answer, the function simply returned a list.

For programming languages supporting flattening infinite lists, this is basically a chameleon duplicate of the Make a list flat challenge.

What the hell, why there's already seven answers on my old post within the last 24 hours? What's going on?

@KevinCruijssen Well, this post is a few years older than the post you linked, so technically the other post is a duplicate of this one, right? ;)

Good point. ;) As for why there are more answers, that's pretty normal. When one person answers it, it'll go to the list of challenges on the home page as recently edited/answered, so more answers will see it and answer as well. :)

Haskell — 70 characters
data N a=N{v::a,c::[N a]}
d n=f[n][]
f(x:y)=f(c x++y).(++[v x])
f _=id

In a more readable format:
data Node a = Node {value::a, children::[Node a]}

dfs :: Node a -> [a]
dfs node = dfs' [node] []
  where dfs' [] result = result
        dfs' (x:xs) result = dfs' (children x ++ xs) (result ++ [value x])

Sample tree:
sampleTree =
    Node 1 [Node 2 [Node 3 [Node 4 [],
                            Node 5 []],
                    Node 6 []],
            Node 7 [],
            Node 8 [Node 9 [Node 10 [],
                            Node 11 []],
                    Node 12 []]]

Sample run:
*Main> dfs sampleTree
[1,2,3,4,5,6,7,8,9,10,11,12]

Haskell, 35 bytes
data D a=T[D a]a
d(T l n)=n:(d=<<l)

Try it online!
data D a=T[D a]a defines a labelled tree data structure. Constructor T takes a list of sub-trees and same value of an arbitrary type a (which however must be consistent throughout each tree).
Here is an example of a tree labelled with integers and the way this tree can be defined using the data structure:
   4
 / | \
1  5  2
  / \
 3   0

tree = T[T[]1, T[T[]3, T[]0]5, T[]2]4

The function d takes such a tree and returns a list of the tree's labels in depth-first order: Calling d tree yields [4,1,5,3,0,2].

Vyxal, 10 1, >2 or 8 bytes
Thanks to @Shaggy and @Kevin Cruijssen!!
If name of nodes are just a primitives (numbers, string) and 1D array is accepted output, than just:
f

If we need to do something with nodes, than:
fƛ<todo>

And if  "A node should be able to contain an infinite number of child nodes":
ƛ:@[vx;f

Try it Online!

ƛ         # Start lambda map
 :        # Duplicate
  @       # Check is array or number (vectorized length==[] if a number)
   [      # Start If
    vx    # If array - vectorized recursive call of lambda
          # Else - do nothing (virtual "|" )
          # Close If (virtual "]" )
        ; # Close lambda
        f # Flatten

I wonder if we're both overthinking this; would simply flattening the input not do the job?

@Shaggy  OMG looks like this! But it is worth checking some test cases. If so it'll be funny!

@Shaggy I thought you were both aware of it, but didn't do so because of the 'infinite' requirement.  Especially because this earlier 8-bytes Vyxal answer (the bottom one) ended with that same flatten f.

Perl, 34
Perl 5.10 or later, run with perl -E'code here':
sub f{ref()?f($_):say for@{$_[0]}}

For example, running f [1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]] produces:
1
2
3
4
5
6
7
8
9
10
11
12

It's Perl 5.10 (and I should have put it in the answer as I usually do), you can either add -M5.010 to the command line, run as -E 'code here', or insert a use 5.010; header do the .pl file.

@Yasir I read the comment (now), but do consider it more convenient to me to print the result instead of returning it.

For older Perl, replace say  with print"$_\n".  Soooo longer.

Yep, it works.  I hurry voted your question twice. You may edit your answer to add notes about Perl version, or even shorter variant of your code in the future, so that I'll be able to vote up ;-)

Japt, 1 byte
... It seems like simply flattening the array will to the job.
c

Try it
Japt, 10 bytes
cÈ¶Ô?ßXÔ:X

Try it
cÈ¶Ô?ßXÔ:X     :Implicit input of multi-dimensional array
c              :Flat map by
 È             :Passing each X through the following function
  ¶            :  Is strictly equal to
   Ô           :  Its reverse, if it's an array, or maximum, if it's an integer (see more detailed explanation below)
    ?          :  If true
     ß         :    Recursive call with argument
      XÔ       :    X reversed (because reversing an array in JS mutates the original)
        :X     :  Else return X

To (try to) explain how the Ô (which is a shortcut for the w method, without any arguments) allows us to differentiate between arrays & numbers by testing for strict equality:
While it's true that in JavaScript 2 arrays containing the exact same elements are not strictly equal as they are 2 distinct objects, an array assigned to a variable is, of course, equal to itself. Add to that that the reverse method for arrays (w in Japt) mutates the original array and that explains how an array assigned to a variable (X in this case) can be strictly equal to its reverse.
As to why a number does not equal its maximum, that's down to a peculiarity of Japt. Firstly, when applied to a number, Japt's w method returns the maximum of that number and the arguments passed to the method, as a Number. However, if no arguments are passed to the w method then the number it's applied to is returned as excpected but, for some reason, Japt converts the returned value to an Object and a Number cannot be strictly equal to an Object

PHP - 57 characters
<?function s($t){echo$t[0].'
';for(;$T=next($t);s($T));}

Test:
s(json_decode('[1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]]'));

Output:
1
2
3
4
5
6
7
8
9
10
11
12

Ruby - 37 35 31 25 characters
s=->t{p t.shift;t.map &s}

Test:
s[[1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]]]

Save 1 by using 'map' instead of 'each'

Scala, 125 bytes
Modified from @Laikoni's Haskell solution.

Golfed version. Try it online!
sealed trait D[A]
case class T[A](l:Seq[D[A]],v:A) extends D[A]
def d[A](t:D[A]):Seq[A]=t match{case T(l,v)=>v+:l.flatMap(d)}

Ungolfed version. Try it online!
object Main {
  sealed trait D[A]
  case class T[A](list: List[D[A]], value: A) extends D[A]

  def d[A](tree: D[A]): List[A] = tree match {
    case T(list, value) => value :: list.flatMap(d)
  }

  val t1 =
    T(
      List(
        T(List(), 1),
        T(
          List(
            T(List(), 3),
            T(List(), 0)
          ),
          5
        ),
        T(List(), 2)
      ),
      4
    )

  def main(args: Array[String]): Unit = {
    println(d(t1))
  }
}

JavaScript, 29 bytes
f=a=>a.flatMap(x=>1/x?x:f(x))

Attempt This Online!

Why not a=>a.flat(1/0)?

05AB1E, 2 (or 13) bytes
˜ε...

The ... indicates something you'd want to do with the item 'name' we're traversing depth-first over.
Try it online with a print statement to verify it's in the correct order, or verify some more test cases.
Try it online with a ragged list containing infinite sub-items.
Explanation:
˜   # Flatten the (implicit) ragged input-list
 ε  # Map over each item:
    #  (do something)

The main rule that stops most other programming languages from using a similar approach is "A node should be able to contain an infinite number of child nodes.". Fortunately, 05AB1E (build in Elixir) supports infinite lists and can flatten them without too much trouble, allowing this approach.
But for completeness sake, here is also a (13 bytes) program if this wouldn't have been possible:
"Ddi...ë®δ.V"©.V

The ... again indicates something you'd want to do with the item 'name' we're traversing depth-first over.
Assumes the 'names' of items used are positive integer ids.
Try it online with a print statement to verify it's in the correct order, or verify some more test cases.
Try it online with a ragged list containing infinite sub-items.
Explanation:
As always, 05AB1E is pretty bad at recursive functions over ragged-lists, and will have to a use a string and evaluate to accomplish this..
"..."     # Push the recursive string explained below
     ©    # Store it in variable `®` (without popping)
      .V  # Evaluate and execute it as 05AB1E code,
          # using the (implicit) input as initial argument

D         # Duplicate the current value
 di       # Pop the copy, and if it's a (non-negative) integer:
   ...    #  (do something)
  ë       # Else (it's a list instead):
    δ     #  Map over the list:
   ® .V   #   Do a recursive call

Actually, I think based on what other submissions have done, just ˜ should be enough.

Go, 89 bytes
import."fmt"
type N struct{v int;c[]N}
func f(n N){Println(n.v)
for _,c:=range n.c{f(c)}}

Attempt This Online!
This code also includes the type definition of a node N. Without it, the code is 63 bytes.
Prints node values to STDOUT, separated by newlines.

Python 3, 52 bytes
def f(t):
 yield t[0]
 for s in t[1]:yield from f(s)

Each node in the tree structure is encoded as a 2-tuple containing a value and an iterable of child nodes. The child nodes iterable may be infinite. Returns a generator containing values. Attempt This Online!
Explanation
def f(t):          # Define generator function f that takes tree t
 yield t[0]        # Yield the value of the root node
 for s in t[1]:    # For each subtree s:
  yield from f(s)  # Apply f to the subtree and yield each value in turn

Using itertools is never the answer.[citation needed] But in this case, it comes pretty close (57 bytes):
lambda t:chain(t[:1],*map(f,t[1]))
from itertools import*

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/2.5/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/