Elixir, 157 148 bytes
-9 bytes from Okx
defmodule N do def f(0,k)do IO.puts 0 end;def f(n,k)do IO.puts n;f Enum.random(0..k),k end end;k=String.to_integer IO.gets"";N.f Enum.random(0..k),k
Try it online!
Formatted:
defmodule N do def f(0,k) do IO.puts n end def f(n,k) do IO.puts n f Enum.random(0..k), k end end {k,_} = Integer.parse IO.gets"" N.f Enum.random(0..k),k
We define a module with 2 functions - one is recursive, the other is the base case with a guard so it only executes when our random is 0 (Elixir doesn't necessarily assign anything, it does pattern matching for e.g. arguments- and thus f(0,k) only matches when n=0, otherwise f(n,k) matches). After defining that module (since functions can't be defined outside a module), we parse an integer from input and start our recursive looping.
Notably, k=String.to_integer IO.gets"" is the same length as the other method I've found to parse integers from input, {k,_}=Integer.parse IO.gets"", which is kinda neat.