Find relevant domain/hosted zone under which to host subdomain Context
In Terraform, to create a new domain record, I first need to find the zone under which it should be hosted.  E.g. If I want to create a DNS record for mysite.example.com, I'd get the zone example.com and create a record for mysite under it, like so:
variable zone {
    type = string
}
variable subdomain {
    type = string
}
variable targets {
    type = list(string)
    default = [&quot;devops.stackexchange.com&quot;] # just defaulting this stuff to reduce code in this sample
}
data aws_route53_zone this {
    name = var.zone
}
resource aws_route53_record this {
    zone_id = data.aws_route53_zone.this.zone_id
    name = &quot;${var.subdomain}.${var.zone}&quot;
    type = &quot;CNAME&quot;
    ttl = 100
    records = var.targets
}
output fqdn {
    value = aws_route53_record.this.fqdn
}

If I wanted to create devops.mysite.example.com then I'd either call this module with:
zone = &quot;example.com&quot;
subdomain = &quot;devops.mysite&quot;

Or, if I had a hosted zone for mysite.example.com, I'd call it with:
zone = &quot;mysite.example.com&quot;
subdomain = &quot;devops&quot;

It's possibly that I could go with the fist approach (e.g. where example.com is my only hosted zone) only for someone to later add a hosted zone for the mysite subdomain.  If that occurred I wouldn't want to have to change my code; since the requirement is still the same; I'd just want Terraform to see that it was still possible to fulfill my requirement (i.e. to create a DNS CName record pointing devops.mysite.example.com at devops.stackexchange.com) and adjust accordingly.
Question
Is there a way to have Terraform determine the appropriated hosted zone for a given record?  E.g. So I could call my module passing devops.mysite.example.com and have the system work its way through the hosted zones recursively until it finds the correct one, then creates the appropriate entry there (or if no appropriate zone was found, error)?
Short answer: I don't believe that is possible.
In my opinion, I suspect this problem has more to do with process and responsibilities than it does with Terraform.
You said:

It's possibly that I could go with the fist approach (e.g. where example.com is my only hosted zone) only for someone to later add a hosted zone for the mysite subdomain. If that occurred I wouldn't want to have to change my code...

Terraform is best when at least most of its associated resources are Terraform-managed. That means you should be managing your zones, too, not just your records.
Which begs the question: why isn't your zone in Terraform?
If your zone was Terraform-managed, the impact of that change should be evident in a terraform plan to anyone who might come along to change it. Even if it references a zone in a different remote state file, a tool like runatlantis.io could show that diff in the Github PR before merging.
Let's say this is the worst-case scenario: you managed the records, it's a different team that creates and manages the zones, and they don't want to use Terraform. In that case, perhaps your DNS records shouldn't be in Terraform, either. Terraform is arguably too stateful for that. Perhaps a few python boto3 scripts can do everything you need it to.