Mutually recursive lists

Question

Let's define a simple function \$f\$ which takes an integer and produces a list:

\$ f(n) = [g(1),g(2),\dots,g(n)] \\ g(n) = [f(0),f(1),\dots,f(n-1)] \$

We can then calculate the first couple of values for \$f(n)\$:

0 ->
 []
1 ->
 [[[]]]
2 ->
 [[[]],[[],[[[]]]]]
3 ->
 [[[]],[[],[[[]]]],[[],[[[]]],[[[]],[[],[[[]]]]]]]
4 ->
 [[[]],[[],[[[]]]],[[],[[[]]],[[[]],[[],[[[]]]]]],[[],[[[]]],[[[]],[[],[[[]]]]],[[[]],[[],[[[]]]],[[],[[[]]],[[[]],[[],[[[]]]]]]]]

And we notice that each one is bigger than the last and has the last list as a prefix to itself.

So we could say that \$f(\infty)\$ is the infinite sequence such that each \$f(n)\$ is the first \$n\$ entries of it.

Now infinite lists of lists of lists ... are a little complicated so instead we will just treat \$f(\infty)\$ as an infinite sequence of opening and closing brackets. The ,s are redundant so we just omit them. In fact we don't need to even deal with the brackets since there are only two values we can make a binary sequence!

1110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000001...
[[[]][[][[[]]]][[][[[]]][[[]][[][[[]]]]]][[][[[]]][[[]][[][[[]]]]][[[]][[][[[]]]][[][[[]]][[[]][[][[[]]]]]]][...

Task

Your task is to output the binary sequence given by \$f(\infty)\$. You can choose any two distinct values for 1 and 0. IO otherwise uses sequence defaults. Read the tag wiki for precise info.

This is code-golf so answers will be scored in bytes with the goal being to minimize your source code size.

Test cases

Here's the first 10000 entries

1110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000000011011100011100110111000001110011011100001101110001110011011100000001110011011100001101110001110011011100000011011100011100110111000001110011011100001101110001110011011100000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000011100110111000011011100011100110111000000110111000111001101110000011100110111000011011100011100110111000000001101110001110011011100000111001101110000110111000111001101110000000111001101110000110111000111001101110000001101110001110011011100000111001101110000110111000111001101110000000000110111000111001101110000011100110111000011011100011100110111000000011100110111000011011100011100110111000000110111000111001101110000011

Answer 1

Haskell, 45 bytes

The top line is a function that returns the nth digit (0-based).

(!!)=<<f 1
f d n=1:(f(1-d)=<<[d..n-1+d])++[0]

Try it online!

The function f generates both \$f(n)\$ with d=1 and \$g(n)\$ with d=0. The top line is a point free version of

h n = f 1 n !! n

where !! is Haskells indexing operator.

Answer 2

JavaScript (ES6), 71 bytes

Returns the \$n\$-th term, 0-indexed.

Very inefficient because it generates way more terms that needed.

n=>(F=n=>n?(g=(n,c=F,h=k=>k>n?0:c(k++)+h(k))=>1+h``)(n-1,g):'10')(n)[n]

Try it online!

Answer 3

Charcoal, 32 bytes

⊞υ10Ｗ¬›Ｌ⌈υ⊗θ⊞υ⪫10⭆υ⪫10⪫…υ⊕λω§⊟υＮ

Try it online! Link is to verbose version of code. Outputs the nth digit (0-indexed). Explanation:

⊞υ10

Start with the base case.

Ｗ¬›Ｌ⌈υ⊗θ

Repeat until the string is way long enough.

⊞υ⪫10⭆υ⪫10⪫…υ⊕λω

Generate the next iteration.

§⊟υＮ

Output the nth value.

Answer 4

Ruby, 59 52 bytes

p(1).step &f=->n,a=0{p 1
n.times{|x|f[x+a,1-a]}
p 0}

Try it online!

• Saved 7 Bytes thanks to @ovs Outputs terms indefinitely on new lines.
  Straightforward approach:

actually saved many bytes by using ovs idea to use just one function behaving differently

p 1           we first print a 1 because we call g(1..) note that we do not need to close an infinite stream.  
1.step &$     again: we call g(1..

$f=->n,a=0    a=0->g() , a=1->f()
{p 1          put a 1: open [
(a...n+a).map{|x|$f[x,1-a]}  inner calls
p 0           put a 0: close ]
```

Answer 5

Haskell, 49 bytes

Since it's been beat here's my original Haskell solution. It takes a radically different approach.

x!y|q<-x++y++[0]=y++0:q!(y++q++[0])
1:[1]![1,1,0]

Try it online!

Looking at this, you can start to see the relationship between the lengths of the terms and the Fibonacci sequence as pointed out by Arnauld.

Answer 6

05AB1E, 19 18 bytes

TλèληJ01ý11ì00«}I£

Outputs the first \$n\$ bits. Could alternatively output the 0-based \$n^{th}\$ bit by replacing the trailing £ with è.
Becomes slower the larger \$n\$ becomes, because it will calculate all bits representing \$f(n)\$ first, before leaving just the first \$n\$.

Try it online.

Could have been shorter if 05AB1E had a to_string function for lists somehow, since ¯¸λèλη (7 bytes) already outputs \$f(n)\$ including commas and spaces.

Try it online.

Explanation:

 λ               # Start a recursive environment
  è              # to output the (implicit) input'th value
T                # Starting with a(0) = "10"
                 # Where every following a(n) is calculated as follows:
   λ             #  Push all previous terms as list: [a(0),a(1),...,a(n-1)]
    η            #  Pop and push the prefixes of this list
     J           #  Join each inner prefix-list together to a string
      01ý        #  Join this list of strings with "01"-delimiter
         11ì     #  Prepend a leading "11" to the string
            00«  #  Append a trailing "00" to the string
 }               # After the recursive function:
  I£             # Leave just the first input amount of digits
                 # (after which the result is output implicitly)