[Question]
  [
The [Cantor function](https://en.wikipedia.org/wiki/Cantor_function) is continuous everywhere and constant [almost everywhere](https://en.wikipedia.org/wiki/Almost_everywhere), but has an average slope of 1:
[![fncantor](https://i.stack.imgur.com/cauCV.png)](https://i.stack.imgur.com/cauCV.png)
The function can be found recursively:
\$f\_0(x)=x\$
\$f\_{n+1}(x)=\left\{\begin{matrix}\frac{1}{2}f\_n(3x)&x\in[0,\frac{1}{3})\\ \frac{1}{2}&x\in[\frac{1}{3},\frac{2}{3})\\ \frac{1}{2}+\frac{1}{2}f\_n(3x-2)&x\in[\frac{2}{3},1] \end{matrix}\right.\$
The Cantor function is the limit of this process, \$\lim\limits\_{n\to\infty} f\_n(x)\$:
[![iteration limit](https://i.stack.imgur.com/JpLpm.gif)](https://i.stack.imgur.com/JpLpm.gif)
# The Challenge
Given real x (which can assume the form of a float or rational number) of the interval \$[0,1]\$ and nonnegative integer n, return \$f\_n(x)\$.
# Rules
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so the shortest answer in bytes wins.
* Assume only valid input will be given.
* Error should be under one ten-thousandth (±0.0001) for the test cases.
# Test Cases
```
In: 0.3 3
Out: 0.3875
In: 0.1 0
Out: 0.1
In: 0.29 4
Out: 0.375
In: 0.11 5
Out: 0.2415625
```
  
[Answer]
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), ~~25~~ 27 bytes
```
{⊥1⊥1⌊⊤1∘≠⍛×\0,3⊤⍵×3*⍺}÷2*⊣
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/v/pR11JDMO7petS1xPBRx4xHnQse9c4@PD3GQMcYKPSod@vh6cZaj3p31R7ebqT1qGvx/7RHbRMe9fY96mo@tN74UdvER31Tg4OcgWSIh2fwf2OFNAUDPWMuAzBtyGUCpo0suUwhAoZcEBXmRlApYyMuXV1dLg0jBaNHvVsMFAw1H3UuNFAwVQA6Rg@oQMGQi0vT382NyzPPCqRcwVhBwb@0BMy2MDeFChsCFcKEDaFiRpYKJnClCJWGQLOhokYmhqZmRqYA "APL (Dyalog Extended) – Try It Online")
Inline tacit function, which can be used as `n f x`.
Uses the method described in [Luis Mendo's MATL answer](https://codegolf.stackexchange.com/a/207417/78410). I changed one part of the algorithm:
* This one doesn't consider integer and fractional parts separately; rather, the fractional part is included in the last digit. (e.g. the base-3 representation of 8.1 is `[2, 2.1]`.) Later, at the step where 2s are changed into 1s, all digits `≥2` are reduced by 1 instead, and **(+2 bytes)** the fractional part of the last digit is removed if its integer part is 1.
```
{⊥1⊥1⌊⊤1∘≠⍛×\0,3⊤⍵×3*⍺}÷2*⊣  ⍝ Left: n, Right: x
{                ⍵×3*⍺}  ⍝ 3^n*x
               3⊤        ⍝ Convert to base 3; last digit may have fractional part
             0,  ⍝ Prepend 0 to avoid error on ⊤ over an empty array
       1∘≠⍛×\    ⍝ Keep each digit unless at least one 1 appears somewhere on its left
      ⊤  ⍝ Convert each digit to binary
    1⌊   ⍝ Clamp all digits >1 to 1 (effectively cuts the fractional part of
         ⍝ the last digit if its integer part is 1)
  1⊥     ⍝ Treat the binary of each digit as base 1 and convert back to a number
         ⍝ Since all numbers are <3, effectively "decrement if ≥2"
 ⊥  ⍝ Treat as base 2 and convert to single number
÷2*⊣  ⍝ Divide by 2^n
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 33 bytes
```
3y^i*1&\3_YAt1=f"O@QJh(wkw]XB+wW/
```
Inputs are `n`, then `x`.
[Try it online!](https://tio.run/##y00syfn/37gyLlPLUC3GOD7SscTQNk3J3yHQK0OjPLs8NsJJuzxcH6iEy0DPGAA) Or [verify all test cases](https://tio.run/##y00syfmf8N@4Mi5Ty1Atxjg@0rHE0DZNyd8h0CtDozy7PDbCSbs8XP@/S8h/Yy4DPSAGkoZcJkDSyJLLFMQxBAA).
## Approach
The code uses a non-recursive approach, based on the procedure for computing the Cantor function \$f\_\infty(x)\$ that appears in [Wikipedia](https://en.wikipedia.org/wiki/Cantor_function#Definition), modified so that it computes \$f\_n(x)\$ instead:
1. Multiply \$x\$ by \$3^n\$.
2. Decompose the result into integer part \$M\$ and decimal part \$F\$.
3. Express \$M\$ in base \$3\$. Let \$B\$ be the resulting sequence of up to \$n\$ digits from the set \$\{0, 1, 2\}\$.
4. If \$B\$ contains a \$1\$, replace every digit after the first \$1\$ by \$0\$.
5. Replace any remaining \$2\$s with \$1\$s.
6. Interpret the result as a binary number.
7. If \$B\$ didn't contain \$1\$s, add \$F\$.
8. Divide by \$2^n\$.
## Some golfing tricks
* Using a `for` loop instead of an `if` branch for step 4 saved quite a few bytes. The value for the branch condition (index of first \$1\$) needed to be used within the branch code (to replace subsequent digits by \$0\$). This is cumbersome in MATL, as the `if` branch consumes (pops) its condition. Instead, the loop solves this more elegantly: since the branch condition was either empty or a vector of indices of \$1\$s in \$B\$, it can be looped over: if it's empty the loop is simply not entered. And then the loop variable can be used within the loop code. The fact that the loop, unlike the conditional branch, may iterate *several* times (if there are more than one \$1\$ digit) is not harmful here, because the substitutions in step 4 are idempotent: they simply overwrite some of the previous \$0\$s with new \$0\$s.
* Step 7 is partly handled within the `for` loop. Specifically, if the loop is entered, the decimal part \$F\$ should not be added later on. To implement this, the loop iteration replaces \$F\$ (previously stored in the stack) by \$0\$. This is done by a round-down operation (`k`), which is convenient because it uses only 1 byte and is, again, idempotent: the result remains equal to \$0\$ in all iterations after the first.
* The MATL function that converts from binary to decimal (`XB`) treats any digit other than \$0\$ as if it were \$1\$, which is useful for steps 5 and 6.
## Commented code
```
3         % Step 1. Push 3
y         % Implicit input: n. Duplicate from below: pushes n below and
          % above the 3
^         % Power: gives 3^n
i*        % Input: x. Multiply: gives x*3^n
1         % Step 2. Push 1
&\        % Two-output modulus: gives modulus (F) and quotient (M)
3_YA      % Step 3. Convert to base 3, with digis 0, 1, 2
t1=       % Step 4 and part of step 7. Duplicate. Compare each entry with 1
f         % Vector (possibly empty) of indices of true values; that is,
          % positions of digit 1
"         % For each index k
  O       %   Push 0
  @Q      %   Push k+1
  Jh(     %   Write 0 at positions k+1, k+2, ..., end
  wkw     %   Swap, round down, swap. This replaces F by 0
]         % End
XB        % Steps 5 and 6. Convert from binary to decimal, with digit 2
          % interpreted as 1
+         % Part of step 7. Add F, or 0
wW/       % Step 8. Swap (brings n to top), 2 raised to that, divide
          % Implicit display
```
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 38 [bytes](https://codegolf.meta.stackexchange.com/questions/9428/when-can-apl-characters-be-counted-as-1-byte-each/)
```
{×⍺×1-⍵:2÷⍨(1∘≤+(1≠⌊)×(⍺-1)∇⊢-⌊)3×⍵⋄⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///v/rw9Ee9uw5PN9R91LvVyujw9ke9KzQMH3XMeNS5RBvI6FzwqKdL8/B0DaAqXUPNRx3tj7oW6YLEjEE6tz7qbgGStf/THrVNeNTb96ir@VHvmke9Ww6tN37UNvFR39TgIGcgGeLhGfzfB6xmlbGCgYKJgimQBGOuIIiwgR5QQs8QiI0sQQwgCwgNFQy5fHSCdDR8FNIOrQjSBAA "APL (Dyalog Unicode) – Try It Online")
Combines the cases of the recurrence using
$$
f\_{n+1}(x) = \frac{1}{2}\begin{cases}
0+1×f\_n(3x-0), x\in[0,1/3) \\
1+0×f\_n(3x-1), x\in[1/3,2/3)\\
1+1×f\_n(3x-2), x\in[2/3,1]
\end{cases}
$$
which can be condensed (note \$u=3x\$) to
$$
f\_{n+1}\left(\frac{1}{3}u\right) = \frac{1}{2}\big(
(u<1)+(\lfloor u\rfloor\neq 1)×f\_n(u-\lfloor u \rfloor)\big)
$$ (since comparisons resolve to True=1 or False=0). This fails for `x=1` since then `⌊u` is 3 instead of 2. Using ceiling instead of floor would then fail for `x=0`, so it ends up shorter to check specifically for `x=1`.
```
{ ... } ⍺=n; ⍵=x
×⍺×1-⍵: ⍝ If n>0 or x≠1:
 3×⍵      ⍝ Let u=3x
  (⍺-1)∇⊢-⌊ ⍝ f(n-1, u-floor(u)) (`1∘|` ←→ `⊢-⌊`)
  (1≠⌊)×    ⍝ Multiply by 1 unless floor(u)=1
  1∘≤+      ⍝ Add 1 unless 1 > u
 2÷⍨      ⍝ Half of this
⋄       ⍝ Else:
 ⍵        ⍝ x
```
[Answer]
# [Python 3](https://docs.python.org/3/), 54 bytes
```
f=lambda n,x:n and(1<x*3<2or x//.5+f(n-1,3*x%1))/2or x
```
[Try it online!](https://tio.run/##LYxBCoNADADvfUUuhY1NXWP0UNHHrMiiYKOIh/T1q7a9DMMcZv3s46KSUuzm8O6HAErWKAQdHLeWSVsuG5j3ef2ITp9MktmdEf23p3iRQGFScEUuJEiXMBU/KV9U/RNTjc0NYN0m3d15I0NMBw "Python 3 – Try It Online")
Python 3 is used just for the `/2` to do float division; Python 2 would be a byte longer with `/2.`.
[Answer]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), 62 bytes
```
f=lambda n,x:n and[f(n-1,e:=3*x),1+e//2*f(n-1,e-2)][e>1]/2or x
```
[Try it online!](https://tio.run/##LYxBCsIwEADvvmKP2bo13URBA/UjpYdIEyzoNoQe4uujxV6GYQ6TPutzEXtNudbYv/z7MXkQKk7AyzREJS1TcL1tChIfg9am2WNrcBzCnUdtlgylxo0EArOA6k6WLNImTN1fzI3Oe2K6oDsApDzLqn5DKoj1Cw "Python 3.8 (pre-release) – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 30 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
_2çH+.
ñH¥.ç<2$?<1$?
×3çɗ⁸⁹?’}
```
A full program accepting \$x\$ and \$n\$ which prints a floating-point representation of \$f\_n(x)\$
**[Try it online!](https://tio.run/##AToAxf9qZWxsef//XzLDp0grLgrDsUjCpS7DpzwyJD88MSQ/CsOXM8OnyZfigbjigbk/4oCZff///y4yOf80 "Jelly – Try It Online")**
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 69 bytes
of course mathematica has a built-in for this: `CantorStaircase[x]` but you cannot choose `n`
```
x_~f~0:=x
x_~f~n_:=If[(y=3x)<1,f[y,n-1]/2,If[y<2,.5,.5+f[y-2,n-1]/2]]
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78/78ivi6tzsDKtoILzMqLt7L1TIvWqLQ1rtC0MdRJi67UydM1jNU30gEKV9oY6eiZApE2kK1rBJWJjf0fUJSZV6LgkBZtoGeso2Acy4UkYKijYIAiYGSpo2CCqgSoxjT2/38A "Wolfram Language (Mathematica) – Try It Online")
*@JonathanAllan saved 2 bytes*
Here is also another approach from @att which is great!
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 57 bytes
```
If[#2<1,#,If[1<3#<2,1,(s=Boole[2#>1])+#0[3#-2s,#2-1]]/2]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b73zMtWtnIxlBHWQfIMrQxVrYx0jHU0Si2dcrPz0mNNlK2M4zV1FY2iDZW1jUq1lE20jWMjdU3ilX7H1CUmVei4JAWbaBnrKNgHMuFJGCoo2CAImBkqaNggqoEqMY09v9/AA "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# JavaScript (ES6), 45 bytes
Expects `(n)(x)`.
```
n=>g=x=>n--?((x*=3)<1?g(x):x<2||1+g(x-2))/2:x
```
[Try it online!](https://tio.run/##fcw9DoJAEEDh3pPMaHbdHykkDHTeg8CywZAdI8RMwd1XsaOhe8WX92w/7dy9x9eiEvchD5QT1ZGE6qRUAyBn8ljZJoJgKZVbV3v5tXKIV1dK7jjNPAU9cYQBPILR3qBe@DFK6KFAPO2J2Yg9JLeNuPsRKf4XuyP5Cw "JavaScript (Node.js) – Try It Online")
### Commented
```
n =>                   // outer function taking n
  g = x =>             // inner recursive function taking x
    n-- ?              // decrement n; if it was not equal to 0:
      (                //   compute f_n(x):
        (x *= 3) < 1 ? //     multiply x by 3; if the result is less than 1:
          g(x)         //       use g(x)
        :              //     else:
          x < 2 ||     //       use 1 if x is less than 2
          1 + g(x - 2) //       otherwise, use 1 + g(x - 2)
      ) / 2            //   in all cases, divide the result by 2
    :                  // else:
      x                //   stop recursion and return f_0(x) = x
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~73~~ \$\cdots\$ ~~71~~ 69 bytes
Saved 4 bytes thanks to the man himself [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld)!!!
```
float f(n,x)float x;{x*=3;x=n--?(x<1?f(n,x):x<2?1:1+f(n,x-2))/2:x/3;}
```
[Try it online!](https://tio.run/##bZHtaoMwFIb/9yoOgpC0sTWxbmuj64@xq1jLEI2b0MWiMsKK1@7yYW33IRhO8j7nPSc5efCW58NQHuusgxJJorCLFT@reRpxlcog2CGV0J2TtyphO7qlC7sNGMYrtlWriPdDJTv4yCqJPuuqwLPzDPSXv2fNHJqXA6Rw9vbqme3V5kn/sUfgdh95PbcZroFOtN2rcmnhMiIQLqlZ2MaGdIRNTYtKhxqQwJpA/MNNqJNQnSgsZA0f7uPJM3IxW9P4jk2JdQPI2FeyEEqnhXwME2irL1GX6OKKV@OBxjGHxcJyGNwLXLswLuO9LHHgE2AKyYss/8guv9WAm8JvRWhluuP/yYU4dpnGWghA3BQuATkpgRCP1DyFgF6ZU6PbK5FnGvQLYu/hlxA8mtVv91KPUupjAi3Rox7t9IstwzCkh7HbftYP3w "C (gcc) – Try It Online")
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), 70 ~~74~~ bytes
*1 byte saved thanks to @FryAmTheEggman*
```
f=lambda n,x:n and((1<=(t:=x*3))+f(n-1,t-2*(t>=2))*(t>=2or 1>t))/2or x
```
[Try it online!](https://tio.run/##NYxBDoIwEEXXcIpZzuCgtNVEieUixkUNaSTBoSFd4OkrRd389/IWP7zjcxJzDnNK3o7u9egdCC@tgJMeUV0txtYulSHaeZRacax1hbGzmujLaQbVRaJDtiX5vAwCg8CtLLDZGwZDvKliaH6qLwzHf177afV7WxZhHiSicD7xG4nSBw "Python 3.8 (pre-release) – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/), 78 bytes
```
sub f{my$b=pop;my$a=pop;$b--?($a<1/3?f(3*$a,$b):$a<2/3?1:1+f(3*$a-2,$b))/2:$a}
```
[Try it online!](https://tio.run/##K0gtyjH9/7@4NEkhrTq3UiXJtiC/wBrISAQzVJJ0de01VBJtDPWN7dM0jLVUEnVUkjStgCJGQBFDK0NtiKiuEUhcU98IKFX7XyXeNs3B7b@BnrGCMZeBnqGCAZA0slQwAXEMFUz/5ReUZObnFf/XLUjMAQA "Perl 5 – Try It Online")
[Answer]
# [R](https://www.r-project.org/), ~~76~~ ... ~~60~~ 58 bytes
*-6 bytes thanks to Robin Ryder, +1 byte to fix bug spotted by Neil, -2 bytes thanks to Giuseppe*
```
f=function(x,n,y=x*3)`if`(n,(min(f(y%%2,n-1),1)+!y<2)/2,x)
```
[Try it online!](https://tio.run/##VczbDoIwDIDhe55ihpBsWg7tmKfIu0BwUy4sCWACT49GDupd@@Vvm7EsuKubbHSZe3LZVTXLHhiGrN9qlVculwzyUbF0cggCAg5RAardZriQigl6Nb@QSaRBK@GL93A8GG9lhGRi/BqdIJ3bvxTBTEwpmj0ZzxcFX0V3t8JebzYsi9a25/UA6FMvO8Z6lsiIBekH13AS9MYX "R – Try It Online")
Un-golfed:
```
cantor=f=function(x,n){
    y=3*x                               # define y=3*x
                                        # to save characters later.
    if(n==0){ x }                       # if n==0 just return x
    else {                              # otherwise
        (
         min(                           # whichever is smaller of:
            cantor(y%%2,n-1),           # - call self using y mod 2
                                        #   (this works for the first & last thirds
                                        #   but gives a result >1 for middle third)
            1)                          # - 1 (to fix the middle third)
         +(y>=2)                        # for the top third we need to add 1 to 
                                        # the result of the self call
        )
        /2                              # finally, we divide all above results by 2
    } 
}
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 35 bytes
```
Ｎθ≔↨×ＮＸ³θ³ηＩ∕↨²Ｅη∧¬№…ηκ¹§⟦ι¹⊖ι⟧ιＸ²θ
```
[Try it online!](https://tio.run/##TY4xD4IwEIV3f0XHu6QagTg5ISwMEgY341DhIo3QQltQf32tmBiHl9zL@@7l1a0wtRad94UaJldO/ZUMjLhfpdbKm4KDsAQn2ZOFfwI5q/QjHAlnIwaXBLXhrTJSOciEdZDLWTb0bYg5O4oBWs5S1UCpA6KnD/iqO8pavUT30BEFpa5QDT3hLIPnLKfaUE/KUQMSL5xJRPwNiJcBiHvvd2y7iSK/nrs3 "Charcoal – Try It Online") Link is to verbose version of code. Based on the Wikipedia entry, I convert the `3ⁿx` to base 3, then massage the digits so that the result can be interpreted as base 2 and divided by `2ⁿ`. Takes input in the order `n`, `x`. Explanation:
```
Ｎθ
```
Input `n`.
```
≔↨×ＮＸ³θ³ηＩ∕
```
Multiply `x` by `3ⁿ` and convert it to base 3. The last entry includes any remaining fractional part.
```
Ｅη∧¬№…ηκ¹§⟦ι¹⊖ι⟧ι
```
Map over the digits. If there was a previous `1` then set this digit to zero, otherwise map the digit to itself, `1`, or subtract `1`, depending on the floor of the digit. This ensures that the last digit (with the remaining fractional part) is converted correctly.
```
Ｉ∕↨²...Ｘ²θ
```
Convert from base 2, divide by `2ⁿ`, and output the final decimal as a string.
Previous 34-byte solution did not work for `x=1`, as it only considered the decimal part of `x`:
```
Ｎθ≔×ＮＸ³θη≔⁻η⌊ηζＦθ≔⊘§⟦ζ¹⊕ζ⟧∕ηＸ³ιζＩζ
```
[Try it online!](https://tio.run/##TY6xDoIwEIZ3n6LjNalGYpyYiMbIgCHGzThUqPQSaKEtaHj5WoNGtrvvvy/3F5KbQvPa@1S1vTv1zV0Y6Gi8SKzFSsEFG2FhHlJGcv0Mw4aRjoZN/q8PtdYGZIBjgBlvJ37GSjrIUPU2JJPx0IaER@RrHnk9iBISl6pSvOAqGYkYSVVhRCOUC5Gktw9wexywFDDOaiClvyK5QeVgx60LAo2935L1Kor8cqjf "Charcoal – Try It Online") Link is to verbose version of code. Takes input in the order `n`, `x`. Explanation:
```
Ｎθ
```
Input `n`.
```
≔×ＮＸ³θη
```
Multiply `x` by `3ⁿ`.
```
≔⁻η⌊ηζ
```
Take the decimal part of that.
```
Ｆθ
```
Loop `n` times.
```
≔⊘§⟦ζ¹⊕ζ⟧∕ηＸ³ιζ
```
Depending on the next base 3 digit of the above product, replace the decimal part with half of itself, half of 1, or half of the sum.
```
Ｉζ
```
Output the final decimal as a string.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 31 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
3Im*1‰`s3в¹£εTYèsi1V]2βY≠i+}¹o/
```
Takes the loose inputs in the order \$n,x\$.
Port of [*@LuisMendo*'s MATL answer](https://codegolf.stackexchange.com/a/207417/52210), so make sure to upvote him as well!
[Try it online](https://tio.run/##AToAxf9vc2FiaWX//zNJbSox4oCwYHMz0LLCucKjzrVUWcOoc2kxVl0yzrJZ4omgaSt9wrlvL///NAowLjI5) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfWVC6H/jiFwtw0cNGxKKjS9siji0@NzWkMjDK4ozDcNqa43ObYp81LkgU7s2Il//v45R2P/oaAM9Yx3jWB0gbahjAKaNLHVMIAKGOqaxsQA).
**Explanation:**
```
3Im              # Push 3 to the power of the first input-integer
   *             # Multiply it by the (implicit) input-decimal
    1‰           # Get the divmod-1 to split the integer and decimal parts
      `s         # Pop and push them separated to the stack in reversed order
3в               # Convert the integer part to base-3 as list
  ¹£             # Only leave the first input-integer amount of base-3 digits
    ε            # Map this list to:
     T           #  Push 10
      Yè         #  Index `Y` into this
                 #  (`Y` is 2 by default, which wraps modulair indices into the 1)
     si          #  If the current digit we're mapping over is 1:
       1V        #   Set `Y` to 1
    ]            # Close both the if-statement and map
     2β          # Convert the resulting list from base-2 to an integer
       Y≠i }     # If `Y` is NOT 1:
          +      #  Add the decimal part that's still on the stack
            ¹o/  # And divide this by 2 to the power the first input-integer
                 # (after which the result is output implicitly)
```
]