It depends on the move.
When using Head Smash, the recoil is 1/2 of the damage dealt. So for example, if Rampardos used Head Smash and did 100 damage to the opponent, then it would get 50 HP recoil. So if the damage dealt is more than double the amount of HP the user has, the user will faint.
Brave Bird, on the other hand, only takes away 1/3 of the damage dealt, so if Brave Bird did 90 damage the user wild lose 30 HP.
There are also moves like High Jump Kick that have Crash Damage, which is a bit different to normal recoil. The amount of recoil doesn't depend on the damage dealt, but with a set amount. If High Jump Kick misses, then the user loses half of its Max HP. This means if the user has an HP stat of 300, then it will lose 150 HP each time it misses a High Jump Kick.
There are also recoil moves that take away only 1/4 of the damage dealt.
Tl;DR: Most commonly, recoil damage is determined by the amount of damage the move did, and the amount varies between moves. You can see a list of recoil moves and their recoil here.