# Background

Famously, the acronym GNU stands for GNU's Not Unix. 1

It's recursive because, after expanding it once, it still contains the acronym GNU, and so must be exanded again:

(GNU's Not Unix)'s Not Unix

And so on, ad infinitum. Visualizing this, we get a kind of Droste effect:

┌────────────────────────────────────────────┬───────────┐
│┌──────────────────────────────┬───────────┐│'s Not Unix│
││┌────────────────┬───────────┐│'s Not Unix││           │
│││┌──────────────┐│'s Not Unix││           ││           │
││││GNU's Not Unix││           ││           ││           │
│││└──────────────┘│           ││           ││           │
││└────────────────┴───────────┘│           ││           │
│└──────────────────────────────┴───────────┘│           │
└────────────────────────────────────────────┴───────────┘

Recursive acronyms need not recurse on the first word, or only once. For example:

• YOPY: Your Own Personal YOPY
• PIPER: PIPER Is PIPER Expanded Recursively

Visualized:

# Challenge

## Input

You will be given two inputs:

1. A string whose space-delimited words form a recursive acronym. That is, if you form a string from the first letter of each word, that string is guaranteed to be either:
• One of the words of the input string (it may occur more than once).
• A prefix of one or more of those words (e.g. GNU is a prefix of GNU's)
• The casing will match exactly
2. A non-negative integer -- the number of times to recursively expand. Given 0, you'll return the input unaltered (or "framed" once, in its entirety). Given 1, you'll expand once. Etc.

## Output

The output is the input string with all instances of the acronym visually expanded, recursively, the specified number of times.

You must use some visual effect to "frame" the nesting -- at minimum, distinct start and end delimiters like parentheses. Ascii boxing of some sort, as in the examples above, is also fine. As would be outputting an actual image that showed the nesting.

I'm flexible as long as the nesting is in fact visualized.

For clarity, parenthesized output would like this:

(((GNU's Not Unix)'s Not Unix)'s Not Unix)'s Not Unix

You are guaranteed that parentheses will never be part of acronym. Other than alphanumeric characters, the acronym will only contain apostrophes, commas, quotes, question marks and exclamation points, and those will only occur as valid punctuation (e.g., a question mark will not appear at the beginning of a word).

This is code golf, fewest bytes wins, no loopholes.

## Test Cases

This assumes you're using a parentheses visualization.

Format for test cases:

1. Input string (the acronym)
2. Input integer (recursion)
3. Expected Output

1. GNU's Not Unix
2. 0
3. GNU's Not Unix

1. GNU's Not Unix
2. 2
3. ((GNU's Not Unix)'s Not Unix)'s Not Unix

1. YOPY Own Personal YOPY
2. 1
3. (YOPY Own Personal YOPY) Own Personal (YOPY Own Personal YOPY)

1. YOPY Own Personal YOPY
2. 2
3. ((YOPY Own Personal YOPY) Own Personal (YOPY Own Personal YOPY)) Own Personal ((YOPY Own Personal YOPY) Own Personal (YOPY Own Personal YOPY))

1. YourYOPY Own Personal YOPY
2. 2
3. YourYOPY Own Personal (YourYOPY Own Personal (YourYOPY Own Personal YOPY))

• looks like a duplicate of this challenge :)
– ngn
Feb 19, 2020 at 6:55
• Next level: visualize mutually recursive acronyms. Eg. “Hurd” → “Hird of Unix-Replacing Daemons” / “Hird” → “Hurd of Interfaces Representing Depth”. Feb 19, 2020 at 12:04
• @Grimmy, Yes, it would. Feb 19, 2020 at 15:45
• @Anush That's absolutely acceptable, even encouraged. Just not required. Feb 19, 2020 at 15:53
• I don't see why we handle YourYOPY Own Personal YOPY as if the YOPY in YourYOPY is not the acronym - the caps seem to imply it should be :/ Feb 19, 2020 at 18:29

# APL (Dyalog Extended), 33 32 bytes

-1 byte thanks to Bubbler.

Anonymous infix lambda. Takes count as left argument and string as right argument.

{('\b',⊃¨⍵⊆⍨≠⍵)⎕R(1⌽')(',⍵)⍣⍺⊢⍵}

Try it online!

{} "dfn"; number is and text is :

⊢⍵ on the text:

⍣⍺ repeat given number of times

()⎕R() PCRE Replace:

')(',⍵ the text prefixed by ")("

1⌽ cyclically rotated one step left (puts ")" at end)

… with:

≠⍵ The mask of non-spaces in the text

⍵⊆⍨ characters runs in the text corresponding to runs of 1s in that

⊃¨ first character of each

'\b', prepend PCRE for word boundary

• I like that rotation trick for the parens Feb 19, 2020 at 7:20
• Unfolding (≠⊆⊢)⍵ into ⍵⊆⍨≠⍵ saves a byte. Actually I was about to post the same thing as a full program, which has the same byte count. Feb 19, 2020 at 7:24

# JavaScript (ES9),  88 85  82 bytes

Takes input as (string)(n).

s=>g=n=>n?s.replace(eval(/\\b${s.match(/(?<=^| )./g).join}/g),(${g(n-1)})):s

Try it online!

### Commented

s =>                       // s = string
g = n =>                 // g is a recursive function taking the counter n
n ?                    // if n is not equal to 0:
s.replace(           //   replace in s:
eval(              //     each word matching:
/\\b${ // a word boundary followed by s.match( // the acronym which consists of /(?<=^| )./g // the letters that are preceded by // either a space or nothing at all ).join // joined together }/g // ), // with: (${               //     the result of
g(n - 1)         //       a recursive call
})                //     surrounded with parentheses
)                    //   end of replace()
:                      // else:
s                    //   end of recursion: just return s
• What level of JavaScript is this??? Feb 23, 2020 at 15:45

# 05AB1E, 2725 22 bytes

ðìÐ#€нJðìs" (ÿ )"Iи.:¦

Try it online!

To make sure we only match the acronym at the beginning of a word, we match an extra leading space. This results in extra spaces in the output, which is allowed.

ðì                      # prepend a space to the input
Ð                     # triplicate
#€нJ                 # acronymize (split on spaces, head of each, join)
ðì               # prepend a space to the acronym
s              # swap
" (ÿ )"       # surround with parentheses
Iи     # repeat the following second-input times:
.:   #  replace the acronym with the parenthesized string
¦  # remove the leading space

# Husk, 20 bytes

!→⁰Ṡ¡§¤σΘom←wJ"()"Θ

Try it online! Takes the number followed by the string. Outputs with parentheses, prefixing each expansion with a space.

### Explanation

!→⁰Ṡ¡§¤σΘom←wJ"()"Θ  (Let X and Y denote the arguments.)
Θ  Take Y prefixed with a space; denote this Y'.
!→⁰                   Take element X + 1 of
Ṡ¡                  the infinite list created by iterating this function on Y':
σ                Take the argument and substitute
m←              the string containing the first character of
Ṡ §      w              each space-separated word of Y',
¤ Θ                prefixed with a space, with
Ṡ §       J           the characters of Y' placed between
"()"        '(' and ')',
¤ Θ                prefixed with a space.

# Perl 6, 48 bytes

{($^s,{S:g/$([~] $s~~m:g/<<./)/($s)/}...*)[$^x]} Try it online! ### Explanation { } # Anonymous block ( , ...*) # Construct infinite sequence$^s                                       # starting with input string.
{                             }  # Compute next item by
S:g/                   /    /   # globally replacing
$( ) # interpolated$s~~m:g/<<./          # first letters of each word
[~]                       # joined (the acronym)
($s) # with input string in parens [$^x]  # Take nth item

# Stax, 11 bytes

û╟;±å↕êg╥σç

Run and debug it

Regex is pretty nice.

## Explanation

D.\bxjMh+x:{R X → input
D             do the following n times, with the first input on stack
.\b          push "\b" (word boundary)
xj        split X on spaces
M       transpose
h      take first row to get abbreviation
+     add that to the boundary
x:{  push X, embedded in braces
R replace matches of the created regex with "(X)"

# Python 3, 104 96 bytes

-7 bytes thanks to @DeathIncarnate, and another -1 byte thanks to @wastl

import re
f=lambda s,n:n and re.sub('\\b'+''.join(c[0]for c in s.split()),f'({s})',f(s,n-1))or s

Try it online!

Explanation:

re.sub(
'\\b'+''.join(c[0]for c in s.split()), # match all acronyms that starts on a word boundary
'('+s+')',                             # replace with the original string in parenthesis
f(s,n-1)                               # on the result of the (n-1)th recursion
)

This is the acronym expanded n times.

return n and recursive_case or base_case

This returns base_case if n is 0, and recursive_case otherwise. This works because in Python, 0 is Falsy and non-empty string is Truthy.

• If n is 0, n and recursive_case short circuits to False, then False or base_case is evaluated which returns base_case.
• If n is not 0, n and recursive_case evaluates to recursive_case which is Truthy, so recursive_case or base_case is short-circuited to recursive_case.
• Obvious saving is to make this a lambda 97 bytes Try it online! Feb 19, 2020 at 19:23
• And using f-strings, there's another byte to be saved: Try it online! Feb 19, 2020 at 19:30
• My understanding of the rules is that 2 bytes can be saved by swapping the lines and moving the f= to the header. Is that correct?
– Seb
Feb 20, 2020 at 16:33
• @Seb Not if it's a recursive function, and in a language that doesn't support anonymous, recursive function calls. For example, Python. Feb 20, 2020 at 19:59
• @mypetlion Makes sense. Thanks for explaining!
– Seb
Feb 20, 2020 at 20:12

# Perl 5-apl, 49 43 bytes

/./,$p.=$&for@F;for$a(1..<>){s/\b$p/(@F)/g}

Try it online!

# Retina, 48 bytes

~($¶($%)
(.).*? (?=.*¶)
$1 ^(.+)¶ 1A¶$1+\b

Try it online! Takes the expansion count and acronym string on separate lines. Explanation:

~(

After performing the script, interpret the result as a new script to be evaluated on the original input.

$¶($%)

Append a space to the string, and append a copy of the string wrapped in ()s on a new line.

(.).*? (?=.*¶)
$1 Turn the string into the acronym. ^(.+)¶ 1A¶$1+\b

Replace the count with a Retina repeat instruction, and also prefix an instruction to delete the count from the original input.

For example, the result of evaluating the inner script on the input 2 GNU's Not Unix is

1A
2+`\bGNU
(GNU's Not Unix)

This deletes the count from the original input, and then performs the acronym expansion twice.

# sed 4.2.2, 180 bytes

h
s/(.)[^ ]* */\1/g
G
s/$/\n/ G h N s/.*\n// tx :l s/^(.*)\n(.*)\b\1(.*)\n(.*)\n(.*)/\1\n\2\n(\5)\3\4\n\5/ tl s/\n(.*)\n(.*)\n/\n\1\2\n\n/ x tx :x s/.// x tl s/.*\n(.*)\n.*\n.*/\1/ Try it online! Well, finding one part of input in another part of input is not that simple in sed. Input is on two lines: first line is the acronym string; second line is number of expansions in unary. • You should be able to include \ns in the capturing groups of your two longest substitutions to save some bytes in the respective replacements Mar 5, 2020 at 18:27 • You can simplify the last substitution using the P command, and shave more bytes by using the -n flag. Also this is sed 4.2.2, so you can use empty labels. All together, you should save 22 bytes Mar 5, 2020 at 18:34 # Python 2, 93 bytes f=lambda s,n:n and re.sub('\\b'+''.join(zip(*s.split())[0]),'('+s+')',f(s,n-1))or s import re Try it online! Similar to a few other answers. If simple substitutions were allowed, I could do... # Python 2, 78 bytes f=lambda s,n:n and f(s,n-1).replace(''.join(zip(*s.split())[0]),'('+s+')')or s Try it online! Except I didn't see the YourYOPY example when I put this together... # PowerShell, 106 bytes function f($a,$n){$s="\b"+(($a.split(" ")|%{$_[0]})-join'')+"\b"
$o=$a;1..$n|%{$a=$a-replace$s,"($o)"};$a}

Try it online!

# PowerShell, 84 71 bytes

Inspired by Wasif

param($n,$a)$o=$a
1..$n*!!$n|%{$a=$a-creplace'\b[A-Z]{2,}\b',"($o)"}$a

Try it online!

# Python 3, 123 106 118 bytes

Rolled back to my initial post.
Chas Brown kindly pointed out I was going down a rabbit hole.
Added 17 bytes to fix word boundary bug.

import re
def f(a,n):
o=a
for i in[1]*n:a=re.sub(r'\b'+''.join([i[0]for i in o.split()])+r'\b',f"({o})",a)
return a

Try it online!

• Clever, but I think this fails for GIGA Is GIGA Again. Feb 20, 2020 at 1:33
• @ChasBrown Oh no! I thought we were only to expand the first instance. T_T Feb 20, 2020 at 8:46