リカバリー失敗

確実な方法としては、レノボに修理依頼をすることです。PCメーカーは、2万円以下の工賃で出荷状態に戻してくれることが多いです。

付属リカバリメディアは、おそらく出荷時にHDDに格納されたリカバリ情報を使用するタイプなのでしょう。市販の消去ツールを使ったため、HDD内のリカバリ情報を破壊してしまった状態です。

Windows8.1proのISOイメージをMicrosoftからダウンロードしてすることは可能ですから、それをDVDに焼いて、DVD起動でインストールしなおす方法はあります。ただ自分でうまくできない方の場合は、やはりメーカー修理に出すべきです。

完全なリカバリーではなくHDDのリカバリー領域からデータを読み取るタイプのリカバリーディスクでは？
もしそうならHDDを完全消去するとアウトです。
PCはただの電源が入る箱になります。

プリインストール版のプロダクトキーではおそらくwindowsのISOファイルは
マイクロソフトからダウンロードできないのでWindows ISO DownLoaderというツールでダウンロードしてください。
ダウンロードしたISOファイルをDVDにISOのままでなくイメージ展開して書き込んでください。
ImgBurnなどで書き込めます。

また、プロダクトキーがPCに貼ってあればそれで再認証が必要になる可能性があります。

Microsoft Windows and Office ISO Download Tool
https://www.heidoc.net/joomla/technology-science/microsoft/67-microsoft-windows-iso-download-tool
Windows ISO DownLoaderでWindowsのISOファイルを公式からダウンロードしよう
https://fwww7.com/2016/09/07/post-3997/

ImgBurn
http://www.imgburn.com/
ImgBurn のインストールと使い方
https://eizone.info/imgburn/

PC を初期状態に戻す
初期状態に戻す操作では、個人用ファイルを保持するか削除するかを選ぶことができます。その後、Windows が再インストールされます。開始するには、[設定]、[更新とセキュリティ]、[この PC を初期状態に戻す]、[開始する] の順に選択し、オプションを選びます。

メモ
設定を開くことができない場合には、サインイン画面から PC を再起動して、PC を初期状態に戻すことができます。Windows ロゴ キー を押しながら L キーを押してサインイン画面を表示し、Shift キーを押しながら、画面の右下隅にある [電源] 、[再起動] の順に選択します。PC が再起動した後、[トラブルシューティング]、[この PC を初期状態に戻す] の順に選択します。

　
データ消去ソフトを使いデータ抹消
これをしたからHDDが未フォーマット状態になってるのです。
データ消去ソフトはHDDに0、1、をランダムに書き込みHDDの中は無法状態になります、だから削除ファイルの復活ができないのです。
こうすると、HDDを管理する部分も無茶苦茶な状態にされてるのでインストールができないのです

HDDを別のパソコンにつなぎフォーマットしてからインストールしてください
　

> こういう場合はどうしたら良いでしょうか？よろしくお願いします。

何故リカバリするしかないと判断されたかです。
この記載がないため、リカバリするのが適切なのか、内蔵HDDのリカバリエリアからのリカバリをしないのはなぜか、
この記載がないため、最悪な事態のリカバリメディアを使ってのリカバリをしている根拠が正しいのかが当方には分かりません。
基本は、内蔵HDDのリカバリエリアからのリカバリが良いとは思います。

Windows 8 / 8.1でWindows（OS）が起動しない状態からハードディスク領域を使用してパソコンの再セットアップを行う方法
http://121ware.com/qasearch/1007/app/servlet/qadoc?QID=014439

上記は、NECサイトですが、レノボーサイトに行き、型番を入れるともっと詳しい説明がありかと思います。
同梱された説明書は読まれていますね。