Brachylog, ¹⁹ 16 bytes

-3 thanks to @Unrelated String

Ḋ|⟨ℕ{√₎|/|-}l⟩↰< 

Try it online!

A recursive function. If n ≥ 10, the three operations are tried. For n < 10 we need n steps to 0. With this we don't have to check that step(n) ≠ n, as it only occurs when there is one digit.

Ḋ|⟨ℕ{√₎|/|-}l⟩↰< Ḋ if n is in 0…9, return n | otherwise ⟨f h g⟩ [f(n), g(n)] h ℕ l [n, digits] and n is a natural number {√₎|/|-} try (root, divide, subtract) one after the other (results that are not natural numbers will get filtered in the next step with ℕ) ↰ recurse < get a number that is strictly larger, thus +1 

R, 77 74 73 bytes

-3 bytes thanks to Giuseppe and -1 byte thanks to MarcMush.

f=function(n,d=nchar(n),k=1:n)`if`(d<2,n,1+f(match(n,c(k^d,k*d,k+d))%%n)) 

Try it online!

Recursive function; avoids floating point issues. The vector k contains all integers from 1 to n. Concatenate k^d, k*d and k+d (yielding a vector of length 3n) and find the position p of the first occurrence of n. Then \$f(n)=1+f(p \mod n)\$. The recursion is initialized by noting that \$f(n)=n\$ for all 1-digit integers (hence the conditioning on d<2).

Works for all the test cases (although 21550 could require you to increase the stack limit on some machines).

APL (Dyalog Extended), 40 36 32 bytes (SBCS)

-6 thanks to ovs.

Anonymous tacit prefix function. Requires zero-based indexing (⎕IO←0).

0∘{×⍵:(1+⍺)∇⊃⍵(…⍤⊣∩√⍨,÷,-)≢⍕⍵⋄⍺} 

Try it online!

0∘{…} "dfn" bound with 0 as left argument (⍺, initial step count ― right argument, \$n\$ is ⍵):

 ×⍵: if \$n>0\$ (lit. "if \$\text{sgn}(n)\$")

 ⍕⍵ stringify \$n\$

 ≢ tally the number of characters (digits)

 ⍵(…) apply the following tacit function to that, with \$n\$ as left argument:

  √⍨ \$\root d\of n\$

  , followed by

  ÷ \$\frac nd\$

  , followed by

  - \$n-d\$

  ∩ intersection of that and

 ⍳⍤⊣ \$\{1,2,3,…,n-1\}\$

⊃ the first element

 (…)∇ recurse on that, with the following as new left argument:

  1+⍺ one plus the current step count

If d←≢⍕⍵ we have the expression ⍵(⍳⍤⊣∩√⍨,÷,-)d which could be written in traditional mathematical notation as:

$$\{1,2,3,…,n-1\}∩\Big\{\root d\of n,\frac nd,n-d\Big\}≡\Big\{\root d\of n,\frac nd,n-d\Big\}\setminus\{n\}$$

JavaScript (ES7),  73  68 bytes

f=n=>(d=(n+'').length)<2?n:1+f((k=n**(1/d)+.5|0)**d-n?n%d?n-d:n/d:k) 

Try it online!

Or 60 bytes if floating point errors are acceptable.

Commented

f = n => // f is a recursive function taking the input n (d = (n + '').length) // d is the number of digits in n < 2 ? // if there's only one digit: n // stop the recursion and return n // (because only n - 1 is valid at this point) : // else: 1 + // increment the final result f( // and do a recursive call: ( // k = n ** (1 / d) // define k as the d-th root of n + .5 | 0 // rounded to the closest integer ) // ** d - n ? // if k ** d is not equal to n: n % d ? // if d is not a divisor of n: n - d // use n - d : // else: n / d // use n / d : // else: k // use k ) // end of recursive call 

Python 3.8, ^{112 \$\cdots\$ 97} 96 bytes

Saved 7 a whopping 15 bytes thanks to Arnauld!!!
Saved a byte thanks to Danis!!!

f=lambda n:n and-~f([t:=round(n**(1/(d:=len(str(n))))),n//d,t,n-d][(t**d!=n)+2*(n%d>0)|3*(d<2)]) 

Try it online!

Julia 0.7, ^{68 62} 57 bytes

inspired by Robin's answer in R

!n=n>0&&1+!filter(r->n∈((d=ndigits(n))r,r+d,r^d),0:n)[] 

Try it online!

Jelly, 19 bytes

*,×;+ ç€DL$œi⁸ḢµƬTL 

Try it online!

How it works

*,×;+ - Helper link. Takes two integers k and d on the left and right * - k * d × - k × d , - [k * d, k × d] + - k + d ; - [k * d, k × d, k + d] ç€DL$œi⁸ḢµƬTL - Main link. Takes n on the left µ - Group the previous links into a monad f(n): $ - To n: D - Cast to digits L - Length € - Over each k = 1, 2, 3, ..., n: ç - Call the helper link with k on the left and the digit length on the right ⁸ - n œi Ḣ - Find the index of the first triple containing n Ƭ - Until reaching a fixed point, repeatedly apply f(n) Both 1 and 0 are fixed points of f(n) As Ƭ returns [n, f(n), f(f(n)), ..., 1] for n > 0 and [0] for n = 0, 1 being a fixed point offsets the included n at the start. However, taking the length here would return 1 for n = 0 instead of 0 T - Find the indices of non-zero elements. As every element is non-zero unless n = 0, this yields [1, 2, ..., l] for n > 0 and [] for n = 0, where l is the output L - Length 

Retina 0.8.2, 134 bytes

.+ ,$&,$&$* +`,(.)*,(1*?)((?=\2+$)(?<=(?=(?<-1>(?=((1*)(?=\2\5+$)1)(\4*$))\6)+1$)\2).*|(?<-1>)(?<-1>\2)+|(?<-1>1)+)$(?(1)1) 1,$.2,$2 1 

Try it online! Link includes faster test cases. Explanation:

.+ ,$&,$&$* 

Create a working area consisting of the result (initially 0), the input, and the input converted to unary.

+` 

Repeat until the input has been reduced to zero ...

,(.)*,(1*?)( 

count the number of digits d in the value n, and then find the smallest value that satisfies one of ...

(?=\2+$)(?<=(?=(?<-1>(?=((1*)(?=\2\5+$)1)(\4*$))\6)+1$)\2).*| 

... its dth power is n, or ...

(?<-1>)(?<-1>\2)+| 

... its product with d is n, or ...

(?<-1>1)+) 

... its sum with d is n, and ...

$(?(1)1) 

ensure that it was in fact d and not some smaller integer, and ...

1,$.2,$2 

increment the output and replace n and its unary with the result.

1 

Convert the output to decimal.

05AB1E, 39 bytes

[D0Q#DUgVXYzmXY/XY-).Δ©D2.òsòQ®XÊ&}ò¼}¾ 

Try it online!

Why can't you try it online? Because there's a bug with the TIO where raising numbers to floats which are actually whole numbers runs infinitely.

Explained

[D0Q#DUgVXYzmXY/XY-).Δ©D2.òsòQ®XÊ&}ò¼}¾ [ # Start an infinite loop with the input already on the stack. D0Q# # End the loop if the result from two lines above is 0 DU # Store the top of the stack in variable X gV # And store its length in variable Y XYzm # Push the Yth root of X XY/ # Push X / Y XY- # Push X - Y ) # And wrap that into a list .Δ # From that list, get the first item where: ©D2.ò # The item, when rounded to 2 decimal places sòQ # Equals the item rounded to the nearest integer ®XÊ& # And where it doesn't equal variable X } # ò # Round that result to the nearest integer ¼} # Increment the counter variable, which keeps track of how many iterations we've gone through ¾ # Push the counter variable and implicitly print 

Charcoal, 34 31 bytes

⊞υＮＷ⌊υ⊞υ⌊Φι№⟦ＸκＬι×κＬι⁺κＬι⟧ιＩ⊖Ｌυ 

Try it online! Link is to verbose version of code. Explanation:

⊞υＮ 

Input n and push it to the predefined empty list.

Ｗ⌊υ 

Repeat until the list contains zero.

⊞υ⌊Φι№⟦ＸκＬι×κＬι⁺κＬι⟧ι 

For all integers less than n, take the dth power and the product and sum with d, and push the lowest integer where one of the results is n to the list.

Ｉ⊖Ｌυ 

Output the final number of iterations, which is one less than the length of the list.

C (gcc) with -lm, 121 120 bytes

• -1 thanks to ceilingcat

To get the number of digits, I used the floor of log10+1 of the value. Each iteration runs through the operations until the result is an integer that doesn't match the current value; when the result is 0 the number of steps is returned.

f(i,c,o,l){float a;for(c=0;i;i=a,c++)for(o=0,l=log10(i)+1,a=.1;fmod(a,1)||a==i;)a=o++?o>2?i-l:(i+0.)/l:pow(i,1./l);i=c;} 

Try it online!

Stax, 47 bytes

ǃô▄↑"è≈■É↑├µxαêöV*┐┘ÆwaYM╙¿9⌠╛o-ºtΓ⌡╔ΔZj♦○Qæº` 

Run and debug it

Accomodates for floating point innacuracies.

Explanation

, put input on main stack

{...w loop till falsy value

X store current interation in register X

c$% get number length

bbbb duplicate number 4 times

u#aa get floating point root

|N get integer root

-Au<{sd}{d}?~ if difference < 0.1, take the integer root otherwise float

/~ get n/d

-~ get n-d

Lr convert all those to array, reverse

{...}j find first value which satisfies:

cx=! not equal to current iteration

_c1u*@=* and not equal to its floor

ciYd save iteration index in Y

y^ output final index

Add++, 82 bytes

D,f,@,BDbLddARdV$€*$G$€+@G$€Ω^BcB]A€ΩedbLRz£*bUBZ@B]A$þ=bU x:? Wx,`x,$f>x,`y,+1 Oy 

Try it online!