# Find the “Recursive Size” of a List

Inspired by Find the “unwrapped size” of a list.

Define the Recursive Size, RS, of a list containing no lists as its length (number of items contained) and the Recursive Size of a list containing any lists as the sum of its length and the Recursive Size of those lists.

### Challenge

Write a program or function that outputs the Recursive Size of any given list in as few bytes as possible.

The input is a list and may contain numbers, strings (if your language has them), and similar lists.

For example:

RS([]) = 0

RS([[]]) = 1

RS([4, 5, 6]) = 3
RS(["four", "five", "six"]) = 3
RS(["[[[[]]]]", "[][][][][]", "][][[[]]][]["]) = 3

RS([[4, 5, 6]]) = 4
RS([["four", "five", "six"]]) = 4
RS([["[[[[]]]]", "[][][][][]", "][][[[]]][]["]]) = 4

RS([, , ]) = 6
RS([["four"], ["five"], ["six"]]) = 6
RS([["[[[[]]]]"], ["[][][][][]"], ["][][[[]]][]["]]) = 6

RS([[[[[[[[[]]]]]]]]]) = 8

RS([[],[],[],[],[],[],[],[]]) = 8

RS([[],[],[[]],[[[[]]]]]) = 8

RS([0,[-1],[2.3,-4.3],[5,],[7,[8,9,[10,11,[12,13,14]]]]]) = 22


Note that if your language has no strings but does have lists of characters, the examples containing "strings" above could actually be lists of characters and have larger results. As an example:

RS([['f','o','u','r'], ['f','i','v','e'], ['s','i','x']]) = 14


This is , so the shortest answer in bytes wins; no funny-business, as always.

A non-list input may produce any output.
I/O is as flexible as usual.

• related – Jonathan Allan Nov 19 '16 at 2:13
• Will the elements be strings, numbers, and recursive lists? – xnor Nov 19 '16 at 2:41
• Note: Restricted the content of the lists after some discussion. I have edited the question to reflect this. Thanks to @xnor for the input! – Jonathan Allan Nov 19 '16 at 3:21
• I feel like this'd be a better challenge without having to account for strings. It's only add bytes to some languages IMO – Conor O'Brien Nov 19 '16 at 5:43
• @ConorO'Brien or maybe I should have made it up to the answerer if they wished to treat a string as a list or not. Unfortunately I specifically asked the community both "Are there any edge cases I should add?", and "Is any clarification of the definition needed?" and got no response in the sandbox over nine days ...and now I suppose such a question would be a duplicate? – Jonathan Allan Nov 19 '16 at 5:54

# Jelly, 8 bytes

ß€-ŒḊ?‘S


Try it online!

### How it works

ß€-ŒḊ?‘S  Main link. Argument: x

ŒḊ?    If x has non-zero depth:
ß€          Recursively map the main link over its elements.
-         Else, yield -1.
‘   Increment all integers in the result.
S  Compute the sum of the result.
If x is an array, incrementing before adding is equivalent to computing
the sum of the elements and the length.
If x is an integer/character, incrementing -1 yields 0, as desired.


## Python, 42 bytes

f=lambda x:x*0==[]and len(x)+sum(map(f,x))


For a non-list, output 0. For a list, output its length plus the sum of the recursive outputs for its elements.

Lists fall above numbers and below strings in the Python 2 ordering, requiring []<=x<''. Instead, we check x*0==[], whereas the result of 0 for a number or '' for a string.

# JavaScript (ES6), 39 37 bytes

Saved 2 bytes thanks to @edc65

f=a=>a.map&&a.map(x=>a-=~f(x),a=0)&&a

• 38 bytes: f=a=>a.map?a.reduce((s,x)=>s+f(x),0):0 – Sethi Nov 20 '16 at 0:58
• @Sethi Wouldn't that return 0 for any input? You have to put a 1 in there somewhere. – ETHproductions Nov 20 '16 at 1:11
• 37: f=a=>a.map&&a.map(x=>a-=~f(x),a=0)&&a. -=~ is 1 char less than +=1+ and, converting a boolean to integer, it cuts another character. Reusing a to avoid the global variable t – edc65 Nov 20 '16 at 8:48
• @edc65 Thanks, that's great! – ETHproductions Nov 25 '16 at 15:02

# Mathematica, 20 bytes

Length@Level[#,∞]&


Anonymous function. Takes an expression as input and returns a number as output. The Unicode character is U+221E INFINITY for \[Infinity]. Level[#,∞] gives a list of the input's subexpressions, and Length@ counts them.

• Boom! Slam dunked on my answer. But I learned something new :) – Greg Martin Nov 19 '16 at 18:42

## Mathematica, 14 bytes

LeafCount@#-1&


Minor modification of my previous answer. As I explained there, LeafCount already takes care of nested atomic values, but it also counts the outermost list, which we need to subtract from the result.

## Perl, 34 bytes

A recursive function! Yep, Perl doesn't only have regex but also have functions!

sub f{@_+f(map ref?@$_:(),@_)if@_}  If you want to test it, you can run something like : perl -pE 'sub f{@_+f(map ref?@$_:(),@_)if@_}$_=f@{+eval}' <<< '[["four"], ["five"], ["six"]]'  # Mathematica, 32 bytes Length@#+Tr[#0/@#~Select~ListQ]&  Unnamed recursive function. The excerpt #0/@#~Select~ListQ calls the function again on each element of the input that's a list, and Tr sums those values up. Fortunately Mathematica is fine taking the length of the empty list and searching for qualifying elements from the empty list, so no base case is needed. ## Haskell, 52 bytes data L a=E a|N[L a] r(N n)=1+sum(r<$>n)
r _=1
pred.r


Usage example:

*Main> pred.r $N[E 0,N[E(-1)],N[E 2.3,E(-4.3)],N[E 5,N[E 6]],N[E 7,N[E 8,E 9,N[E 10,E 11,N[E 12,E 13,E 14]]]]] 22  Haskell doesn't support mixed lists (e.g. Int and list of Int), so I go with a custom list type L which is either an element of some type a (-> E a) or a list of other Ls (-> N[L a]). Calculating the RS is a simple recursion where an E counts 1 and a N one plus the sum of the recursive sizes of its elements. The whole sum is off by 1, so I subtract it via pred. Side note: the exact types and values of the elements are not important for the algorithm, so we could remove the polymorphism an deal with abstract elements only and go with data L=E|N[L]. # Factor, 105 bytes Recursive function g. : g ( o -- l ) [ dup [ sequence? ] [ string? not ] bi and [ [ g ] map sum 1 + ] [ drop 1 ] if ] map sum ;  Ungolfed (kinda): : g ( o -- l ) [ dup [ sequence? ] [ string? not ] bi and [ [ g ] map sum 1 + ] [ drop 1 ] if ] map sum ;  You'll find there are no calls to length because instead of using the length builtin, it's implemented through drop 1 on strings and non-sequences. ## Mathematica, 18 bytes (c=-1;++c&//@#;c)&  Yet another Mathematica approach. Not as short as using the built-in LeafCount but still fairly concise. This makes use of the MapAll operator //@ which calls a function on every node of an expression, and we use that function to increment a counter c. As in the LeafCount case, this gives one more than we need, because it counts the outer list head as well, so we start the counter from -1. # C# (Visual C# Interactive Compiler), 50 bytes int f(Array a)=>a.Length+a.OfType<Array>().Sum(f);  Try it online! Uses the same technique as the previously submitted Java answer, but leverages LINQ to reduce the answer length. Explanation: // f is a method that a accepts // an array of any underlying type int f(Array a)=> // include the length of the // current array in the total a.Length+ // filter the current list to elements // that are also arrays a.OfType<Array>() // recursively call f on each child // array and add to cumulative total .Sum(f);  # 05AB1E (legacy), 22 17 bytes "ε¼D¸D˜Êi®.V"©.V¾  Explanation: This challenge poses multiple challenges to overcome in 05AB1E: 1. Although 05AB1E does have a recursive function since the Elixir rewrite (λ), it's only useful for integer sequences. Here is an answer of mine as example of the 05AB1E recursive function. Because of that, I had to find an alternative to do recursive calls, which I did by putting part of the code in a string, and execute that string as 05AB1E code recursively. 2. There also isn't an isList command in 05AB1E, so I had to use some workarounds to check this by utilizing wrapping into a list, deep flattening, and check for equality. 3. And third, there isn't a flatten for just one level of a multi-dimensional list. The flatten function ˜ is a deep flatten that removes all layers and makes a multi-dimensional list a single list with all inner-most values. (i.e. [[1,2],[[],4]] becomes [1,2,3,4]). I ended up with the code at the top to overcome all three of the above issues. It's split into three major parts. First we have the following: "..." # Create a string with 05AB1E code © # Save this string in the register (without popping) .V # Execute the string as 05AB1E code  The string contains the following code: ε # Map each value in the given list by: # (this uses the input-list implicitly with the initial call) ¼ # Increase the counter_variable by 1 D # Duplicate the map-value # i.e. STACK "A" becomes "A","A" # i.e. STACK [["B","C"]] becomes [["B","C"]],[["B","C"]] ¸ # Wrap it into a list # i.e. "A" → ["A"] # i.e. [["B","C"]] → [[["B","C"]]] D # Duplicate that again # i.e. STACK "A",["A"] becomes "A",["A"],["A"] # i.e. STACK [["B","C"]],[[["B","C"]]] # becomes [["B","C"]],[[["B","C"]]],[[["B","C"]]] ˜ # Flatten it # i.e. ["A"] → ["A"] # i.e. [[["B","C"]]] → ["B","C"] Ê # Check if the wrapped and wrapped+flattened lists are NOT equal # i.e. ["A"] and ["A"] → 0 (falsey) # i.e. [[["B","C"]]] and ["B","C"] → 1 (truthy) i # If they are: ® # Push the string from the register .V # Execute it as 05AB1E code # (this is basically our recursive call, mapping the current value # we duplicated initially again)  A map is used instead of a foreach-loop, because the map has an implicit y, and a foreach-loop need an explicit y. We only care about the counter_variable, though. And finally, after all the maps and inner maps are done, we'll: ¾ # Push the counter_variable (which is output implicitly as result)  # R, 65 bytes R=function(L,*=sapply)"if"(any(L*is.list),sum(1+L*R),length(L))  Try it online! Obvious recursive implementation of the spec. # C, 174167 152 bytes Recursive function f, which leaks memory (152): #include"object.h" size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t*o=array_get_copy(a,i,0);t+=o->type==6?f(o->ary):1;}return t;}  Recursive f which doesn't leak, using references, at 167: #include"object.h" size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t**o=array_get_ref(a,i,0);t+=*o->type==t_array?f(*o->ary):1;}return t;}  Ungolfed: size_t get_recursize (const array_t* const a) { pfn(); object_failnull(a); size_t out = 0; for (size_t i = 0; i < array_length(a); i++) { object_t** o = array_get_ref(a, i, NULL); if ( (*o)->type == t_array ) { out += get_recursize((*o)->ary); } else { ++out; } } return out; }  "But how," you ask, "can this be answered in C? Surely, there are no managed arrays in C, and you can't really have heterogeneous arrays...?" "Aha," I reply, "for I have been working on a simple system of "objects" for (GNU-ish) C11 and ISO C++11". The full demo program for this function is: #include "../calc/object/object.h" size_t get_recursize (const array_t* const a); define_array_new_fromctype(ssize_t); int main (void) { size_t len = 6; static const ssize_t h = { -1, 3, -5, 7, -9, 11 }; array_t* a = array_new_from_ssize_t_lit(h, len, t_realint); size_t rsize = get_recursize(a); printf("Recursive size of a: %zu\n", rsize); object_t* asobj = object_new(t_array, a); array_destruct(a); array_t* b = array_new(NULL, -1); for (size_t j = 0; j < 10; j++) { array_append(b, asobj); } object_destruct(asobj); rsize = get_recursize(b); printf("Recursive size of b: %zu\n", rsize); asobj = object_new(t_array, b); array_destruct(b); array_t* c = array_new(NULL, -1); for (size_t i = 0; i < 100; i++) { array_append(c, asobj); } object_destruct(asobj); rsize = get_recursize(c); printf("Recursive size of c: %zu\n", rsize); array_destruct(c); return EXIT_SUCCESS; } size_t get_recursize (const array_t* const a) { pfn(); object_failnull(a); size_t out = 0; for (size_t i = 0; i < array_length(a); i++) { object_t** o = array_get_ref(a, i, NULL); if ( (*o)->type == t_array ) { out += get_recursize((*o)->ary); } else { ++out; } } return out; }  Right now, it lives here and you'll need that repo to use this. You'll also need the Fowler-Noll-Vo hash library, libfnv, compiled for your platform. It's in that repository and you can also grab it here. Then you can do cc -DNODEBUG size.c path/to/libfnv.a -o size. The implementation isn't necessarily efficient: $ valgrind --leak-check=full --track-origins=yes --show-leak-kinds=all ./size
==24127== Memcheck, a memory error detector
==24127== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==24127== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==24127== Command: ./size
==24127==
Recursive size of a: 6
Recursive size of b: 60
Recursive size of c: 6000
==24127==
==24127== HEAP SUMMARY:
==24127==     in use at exit: 0 bytes in 0 blocks
==24127==   total heap usage: 22,900 allocs, 22,900 frees, 615,584 bytes allocated
==24127==
==24127== All heap blocks were freed -- no leaks are possible
==24127==
==24127== For counts of detected and suppressed errors, rerun with: -v
==24127== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)


But it does work! The last commit to master (which this program compiled on) was 2 days ago, which means this submission is valid.

Axiom 118 bytes

RS(a:Union(List(Any),Any)):INT==(a case List(Any)=>(g:List(Any):=a;leaf? g=>0;r:=#g;for i in g repeat r:=r+RS(i);r);0)


ungolfed

RS(a:Union(List(Any),Any)):INT==
a case List(Any)=>
g:List(Any):=a
leaf? g=>0
r:=#g
for i in g repeat r:=r+RS(i)
r
0


results

(25) -> RS([])=0
(25)  0= 0
Type: Equation NonNegativeInteger
(26) -> RS([[]]) = 1
(26)  1= 1
Type: Equation PositiveInteger
(27) -> RS([4, 5, 6]) = 3
(27)  3= 3
Type: Equation PositiveInteger
(28) -> RS(["four", "five", "six"]) = 3
(28)  3= 3
Type: Equation PositiveInteger
(29) -> RS(["[[[[]]]]", "[][][][][]", "][][[[]]][]["]) = 3
(29)  3= 3
Type: Equation PositiveInteger
(30) -> RS([[4, 5, 6]]) = 4
(30)  4= 4
Type: Equation PositiveInteger
(31) -> RS([["four", "five", "six"]]) = 4
(31)  4= 4
Type: Equation PositiveInteger
(32) -> RS([["[[[[]]]]", "[][][][][]", "][][[[]]][]["]]) = 4
(32)  4= 4
Type: Equation PositiveInteger
(33) -> RS([, , ]) = 6
(33)  6= 6
Type: Equation PositiveInteger
(34) -> RS([["four"], ["five"], ["six"]]) = 6
(34)  6= 6
Type: Equation PositiveInteger
(35) -> RS([["[[[[]]]]"], ["[][][][][]"], ["][][[[]]][]["]]) = 6
(35)  6= 6
Type: Equation PositiveInteger
(36) -> RS([[[[[[[[[]]]]]]]]]) = 8
(36)  8= 8
Type: Equation PositiveInteger
(37) -> RS([[],[],[],[],[],[],[],[]]) = 8
(37)  8= 8
Type: Equation PositiveInteger
(38) -> RS([[],[],[[]],[[[[]]]]]) = 8
(38)  8= 8
Type: Equation PositiveInteger
(39) -> RS([0,[-1],[2.3,-4.3],[5,],[7,[8,9,[10,11,[12,13,14]]]]]) = 22
(39)  22= 22
Type: Equation PositiveInteger
(40) -> RS([['f','o','u','r'], ['f','i','v','e'], ['s','i','x']]) = 14
(40)  14= 14
Type: Equation PositiveInteger


# APL(NARS), 24 chars, 48 bytes

{⍬≡⍵:0⋄×≡⍵:(≢⍵)++/∇¨⍵⋄0}


This would be the litteral traslation of 'my' Axiom answer here... In APL the void list would be ´⍬´ Zilde, that you indicate with ´[]´, ´⊂⍬´ is ´[[]]´, ´1 2 3´ is ´[1,2,3]´ ecc Some test:

  RS←{⍬≡⍵:0⋄×≡⍵:(≢⍵)++/∇¨⍵⋄0}
RS ⍬
0
RS ⊂⍬
1
RS  4 5 6
3
RS ("four")("five")("six")
14
RS ('f' 'o' 'u' 'r') ('f' 'i' 'v' 'e') ('s' 'i' 'x')
14
RS ("(((())))")("()()()()()")(")()((()))()(")
33
RS (⊂4 5 6)
4
RS (⊂("four")("five")("six"))
15
RS (⊂("(((())))")("()()()()()")(")()((()))()(") )
34
RS (,4) (,5) (,6)
6
RS ⊂¨("four")("five")("six")
17
RS ⊂¨("(((())))")("()()()()()")(")()((()))()(")
36
RS ⊂⊂⊂⊂⊂⊂⊂⊂⍬
8
RS ⍬⍬⍬⍬⍬⍬⍬⍬
8
RS ⍬⍬(⊂⍬)(⊂(⊂(⊂⍬)))
8
RS 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))
22


for print the other type of results the exercise propose we need one other function (both functions RS and Rs should be ok for the exercise)

  Rs←{⍬≡⍵:0⋄(''≡0↑⍵)∨0=≡⍵:0⋄(≢⍵)++/∇¨⍵}
Rs ("four")("five")("six")
3
Rs ("(((())))")("()()()()()")(")()((()))()(")
3
Rs (⊂("four")("five")("six"))
4
Rs (⊂("(((())))")("()()()()()")(")()((()))()(") )
4
Rs ⊂¨("four")("five")("six")
6
Rs ⊂¨("(((())))")("()()()()()")(")()((()))()(")
6
Rs 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))
22
Rs ('f' 'o' 'u' 'r') ('f' 'i' 'v' 'e') ('s' 'i' 'x')
3


for see how appear some input we use the o function:

  o←⎕fmt
o 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))
┌5─────────────────────────────────────────────────────────┐
│  ┌1──┐ ┌2────────┐ ┌2─────┐ ┌2──────────────────────────┐│
│0 │ ¯1│ │ 2.3 ¯4.3│ │  ┌1─┐│ │  ┌3──────────────────────┐││
│~ └~──┘ └~────────┘ │5 │ 6││ │7 │    ┌3────────────────┐│││
│                    │~ └~─┘2 │~ │8 9 │      ┌3────────┐││││
│                    └∊─────┘ │  │~ ~ │10 11 │ 12 13 14│││││
│                             │  │    │~~ ~~ └~────────┘2│││
│                             │  │    └∊────────────────┘3││
│                             │  └∊──────────────────────┘4│
│                             └∊──────────────────────────┘5
└∊─────────────────────────────────────────────────────────┘


this print Zilde, and one 8 Zilde list:

  o ⍬
┌0─┐
│ 0│
└~─┘
o ⍬⍬⍬⍬⍬⍬⍬⍬
┌8──────────────────────────────────────┐
│┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐│
││ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0││
│└~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘2
└∊──────────────────────────────────────┘


# Java, 96 bytes

int c(Object[]a){int r=a.length;for(var i:a)r+=i instanceof Object[]?c((Object[])i):0;return r;}


Try it online.

Explanation:

int c(Object[]a){  // Recursive method with Object-array parameter and integer return-type
int r=a.length;  //  Result-sum, starting at the size of the input-array
for(var i:a)     //  Loop over the input-array:
r+=            //   Increase the result-sum by:
i instanceof Object[]?
//    If the current item is an array:
c((Object[])i)
//     A recursive call with this item
:           //    Else:
0;         //     0 (so leave the result-sum the same)
return r;}       //  Return the result-sum


# Attache, 21 bytes

{#_+Sum!\$=>IsArray\_}


Try it online!

Turns out the C# approach is pretty short in Attache.

## Alternatives

25 bytes f[x]:=#x+Sum!f=>IsArray\x

26 bytes f[x]:=#x+Sum[f=>IsArray\x]

35 bytes f:=Sum##{If[IsArray@_,1+f@_,1]}=>Id

35 bytes f:=Sum@Map[{If[IsArray@_,1+f@_,1]}]

37 bytes f[x]:=Sum[{If[IsArray@_,1+f@_,1]}=>x]

Clojure, 79 77 51 bytes

Input has to be a list, not vector. Both would be supported by using sequential?.

(defn f[i](if(seq? i)(apply +(count i)(map f i))0))


Previous:

(defn f[i](if(seq? i)(if(some seq? i)(apply +(count i)(map f i))(count i))0))


# Python, 72 bytes

l=lambda a:0if len(a)==0else len(a)+sum(l(i)for i in a if type(i)==list)

• you can remove some spaces there – Blue Dec 29 '16 at 18:44
• Specifically, between 0 and if, 0 and else, and ) and for. – Zacharý Dec 29 '16 at 21:54
• If you need rep for your chat bot account, consider making a meaningful contribution to the site. This adds absolutely nothing over the pre-existing 42 byte Python answer. – Dennis Dec 29 '16 at 22:33