Find the substring avoiding the use of recursive function

We can see that the string represented by x(k) grows exponentially in length with increasing k:

len(x(1)) == 3
len(x(k)) == len(x(k-1)) * 2 + 3

So:

len(x(k)) == 3 * (2**k - 1)

For k equal to 100, this amounts to a length of more than 10³⁰. That's more characters than there are atoms in a human body!

Since the parameters s and t will take (in comparison) a tiny, tiny slice of that, you should not need to produce the whole string. You can still use recursion though, but keep passing an s and t range to each call. Then when you see that this slice will actually be outside of the string you would generate, then you can just exit without recursing deeper, saving a lot of time and (string) space.

Here is how you could do it:

def getslice(k, s, t):
    def recur(xsize, s, t):
        if xsize == 0 or s >= xsize or t <= 0:
            return ""
        smaller = (xsize - 3) // 2
        return ( ("1" if s <= 0 else "")
               + recur(smaller, s-1, t-1)
               + ("2" if s <= smaller+1 < t else "")
               + recur(smaller, s-smaller-2, t-smaller-2)
               + ("3" if t >= xsize else "") )
    return recur(3 * (2**k - 1), s, t)

This doesn't use any caching of x(k) results... In my tests this was fast enough.

This is an interesting problem. I'm not sure whether I'll have time to write the code, but here's an outline of how you can solve it. Note: see the better answer from trincot.

As discussed in the comments, you cannot generate the actual string: you will quickly run out of memory as k grows. But you can easily compute the length of that string.

First some notation:

f(k) : The generated string.
n(k) : The length of f(k).
nk1  : n(k-1), which is used several times in table below.

For discussion purposes, we can divide the string into the following regions. The start/end values use standard Python slice numbering:

Region | Start         | End           | Len | Subtring | Ex: k = 2
-------------------------------------------------------------------
A      | 0             | 1             | 1   | 1        | 0:1  1
B      | 1             | 1 + nk1       | nk1 | f(k-1)   | 1:4  123
C      | 1 + nk1       | 2 + nk1       | 1   | 2        | 4:5  2
D      | 2 + nk1       | 2 + nk1 + nk1 | nk1 | f(k-1)   | 5:8  123
E      | 2 + nk1 + nk1 | 3 + nk1 + nk1 | 1   | 3        | 8:9  3

Given k, s, and t we need to figure out which region of the string is relevant. Take a small example:

k=2, s=6, and t=8.

The substring defined by 6:8 does not require the full f(k). We only need
region D, so we can turn our attention to f(k-1).

To make the shift from k=2 to k=1, we need to adjust s and t: specifically,
we need to subtract the total length of regions A + B + C. For k=2, that
length is 5 (1 + nk1 + 1).

Now we are dealing with: k=1, s=1, and t=3.

Repeat as needed.

Whenever k gets small enough, we stop this nonsense and actually generate the string so we can grab the needed substring directly.

It's possible that some values of s and t could cross region boundaries. In that case, divide the problem into two subparts (one for each region needed). But the general idea is the same.

Based on @FMc's answer, here's some python3 code that calculates x(k, s, t):

from functools import lru_cache
from typing import *


def f_len(k) -> int:
    return 3 * ((2 ** k) - 1)


@lru_cache(None)
def f(k) -> str:
    if k == 1:
        return "123"
    return "1" + f(k - 1) + "2" + f(k - 1) + "3"


def substring_(k, s, t, output) -> None:
    # Empty substring.
    if s >= t or k == 0:
        return

    # (An optimization):
    # If all the characters need to be included, just calculate the string and cache it.
    if s == 0 and t == f_len(k):
        output.append(f(k))
        return

    if s == 0:
        output.append("1")

    sub_len = f_len(k - 1)
    substring_(k - 1, max(0, s - 1), min(sub_len, t - 1), output)

    if s <= 1 + sub_len < t:
        output.append("2")

    substring_(k - 1, max(0, s - sub_len - 2), min(sub_len, t - sub_len - 2), output)

    if s <= 2 * (1 + sub_len) < t:
        output.append("3")


def substring(k, s, t) -> str:
    output: List[str] = []
    substring_(k, s, t, output)
    return "".join(output)


def test(k, s, t) -> bool:
    actual = substring(k, s, t)
    expected = f(k)[s:t]
    return actual == expected


assert test(1, 0, 3)
assert test(2, 2, 6)
assert test(2, 1, 5)
assert test(2, 0, f_len(2))
assert test(3, 0, f_len(3))
assert test(8, 44, 89)
assert test(10, 1001, 2022)
assert test(14, 12345, 45678)
assert test(17, 12345, 112345)
# print(substring(30, 10000, 10100))
print("Tests passed")

Here's a commented iterative version in JavaScript that's very easy to convert to Python.

In addition to being what you asked for, that is non-recursive, it allows us to solve things like f(10000, 10000, 10050), which seem to exceed Python default recursion depth.

// Generates the full string
function g(k){
  if (k == 1)
    return "123";
  prev = g(k - 1);
  return "1" + prev + "2" + prev + "3";
}

function size(k){
  return 3 * ((1 << k) - 1);
}

// Given a depth and index,
// we'd like (1) a string to
// output, (2) the possible next
// part of the same depth to
// push to the stack, and (3)
// possibly the current section
// mapped deeper to also push to
// the stack. (2) and (3) can be
// in a single list.
function getParams(depth, i){
  const psize = size(depth - 1);

  if (i == 0){
    return ["1", [[depth, 1 + psize], [depth - 1, 0]]];
    
  } else if (i < 1 + psize){
    return ["", [[depth, 1 + psize], [depth - 1, i - 1]]];
    
  } else if (i == 1 + psize){
    return ["2", [[depth, 2 + 2 * psize], [depth - 1, 0]]];
    
  } else if (i < 2 + 2 * psize){
    return ["", [[depth, 2 + 2 * psize], [depth - 1, i - 2 - psize]]];
    
  } else {
    return ["3", []];
  }
}

function f(k, s, t){
  let len = t - s;
  let str = "";
  let stack = [[k, s]];
  
  while (str.length < len){
    const [depth, i] = stack.pop();

    if (depth == 1){
      const toTake = Math.min(3 - i, len - str.length);
      str = str + "123".substr(i, toTake);
      
    } else {
      const [s, rest] = getParams(depth, i);
      str = str + s;
      stack.push(...rest);
    }
  }
  
  return str;
}

function test(k, s, t){
  const l = g(k).substring(s, t);
  const r = f(k, s, t);
  console.log(g(k).length);
  //console.log(g(k))
  console.log(l);
  console.log(r);
  console.log(l == r);
}

test(1, 0, 3);
test(2, 2, 6);
test(2, 1, 5);
test(4, 44, 45);
test(5, 30, 40);
test(7, 100, 150);