「そもそも整数の割り算ってなに?」って人も多いだろうと思う(あるいは知ってるけど案外知らなかったり)ので定義しておくと、2 つの整数 𝒛₁ と 𝒛₂(ただし 𝒛₂ ≠ 0)があったとき、𝒛₁ = 𝒒𝒛₂ + 𝒓(ただし 0 ≦ 𝒓 < |𝒛₂|)を満たすただ一通りの 𝒒 と 𝒓 の組を求めることを「𝒛₁ を 𝒛₂ で割る」というのね(𝒒 を商といい 𝒓 を剰余あるいは余りという)
※いま(ただし 0 ≦ 𝒓 < |𝒛₂|)って書いたけどこれは一般的というだけで 𝒒 と 𝒓 が一意に定まるなら条件はなんでもいい。実際プログラミング言語に実装されてる剰余演算では平気で負の余り返したりする

正の数同士なら「引けるだけ引く法」で解けるんだけど負が絡んでくると面倒でいろいろ試した。それで、|𝒛₁| = |𝒛₂| あるいは |𝒛₁| < |𝒛₂| の場合、その具体的な値によらず 𝒛₁ と 𝒛₂ の符号によって 𝒒 が定まることに気づきました(遅い)

まず、|𝒛₁| = |𝒛₂| のとき、𝒛₁ の符号と 𝒛₂ が同じなら 𝒒 = 1、異なるなら 𝒒 = -1。これは絶対。
そして |𝒛₁| < |𝒛₂| のとき、𝒛₁ ≧ 0 なら 𝒒 = 0、𝒛₁ < 0 なら 𝒛₂ = ±𝒏 として 𝒒 = ∓1(つまり符号が逆な 1)になる。

ここまでくれば 𝒛₁ / 𝒛₂ = (𝒛₁ - 𝒛₂) / 𝒛₂ + 1 = (𝒛₁ + 𝒛₂) / 𝒛₂ - 1 は常に成り立つ(はずな)ので、(𝒛₁ - 𝒛₂)と(𝒛₁ + 𝒛₂)のうち絶対値が小さい方を再帰呼び出しすればよいわけです!
※"/"は 𝒒 のみを求める演算だと思ってください

最後に 𝒓 は定義より 𝒛₁ - 𝒒𝒛₂ なのでイエーイ沖田さん大勝利～!