Faster alternative to scalar UDF with recursion to walk tree hierarchy?

I have a scalar function that traverses a simple parent-child hierarchy of customers to find the ancestor that's in charge of billing. Here's a simplified version of the schema.

CREATE TABLE Customer (CustomerID int, ParentCustomerID int, IsBillToCustomer bit)

The UDF walks up the chain until it hits the top parent, recording the IsBillToCustomer setting for each customer in the chain, then returns the CustomerID for the highest customer in the chain with IsBillToCustomer = 1. The UDF is fast for each customer, but I need to run reports that return thousands of customers with data associated to their billing master and it takes tens of minutes for so many customers. Is my only alternative to implement SQL Server's hierarchyID data type? Will that even help?

Creating a SQL job that stores the data I need is not a viable solution because the data needs to be as up-to-date as possible and I can't be running a 40-minute CPU-intensive job over and over.

UPDATE: I created a temporary table using HierarchyID and set up some indexes, then used IsDescendantOf in my query, and it still took over 13 minutes (and hammered my CPU's).

Let's start with this. Let us know if it looks something like this. Please edit as necessary. I am adding data into the table:

INSERT INTO Customer (CustomerID, ParentCustomerID, IsBillToCustomer)
select  1   ,   0   ,   0   union all
select  2   ,   0   ,   0   union all
select  3   ,   0   ,   0       union all
select  4   ,   1   ,   0   union all
select  5   ,   2   ,   0   union all
select  6   ,   3   ,   1   union all
select  7   ,   1   ,   1   union all
select  8   ,   2   ,   1   union all
select  9   ,   3   ,   1   union all
select  10  ,   1   ,   0   union all
select  11  ,   2   ,   0   union all
select  12  ,   3   ,   0   union all
select  13  ,   1   ,   0   union all
select  14  ,   2   ,   0   union all
select  15  ,   3   ,   1   union all
select  16  ,   1   ,   1   union all
select  17  ,   2   ,   1   union all
select  18  ,   3   ,   1   union all
select  19  ,   1   ,   0   union all
select  20  ,   2   ,   1   union all
select  21  ,   3   ,   1   union all
select  22  ,   1   ,   1   union all
select  23  ,   2   ,   0   union all
select  24  ,   3   ,   0   union all
select  25  ,   1   ,   1   union all
select  26  ,   2   ,   1   union all
select  27  ,   3   ,   1   union all
select  28  ,   1   ,   1   union all
select  29  ,   2   ,   0   union all
select  30  ,   3   ,   0   union all
select  31  ,   1   ,   0   union all
select  32  ,   2   ,   0   union all
select  33  ,   3   ,   0   union all
select  34  ,   1   ,   1   union all
select  35  ,   2   ,   1   union all
select  36  ,   3   ,   1   union all
select  37  ,   1   ,   1   union all
select  38  ,   2   ,   0   union all
select  39  ,   3   ,   1   union all
select  40  ,   1   ,   1   union all
select  41  ,   2   ,   1   union all
select  42  ,   3   ,   0   union all
select  43  ,   1   ,   0   union all
select  44  ,   2   ,   1   union all
select  45  ,   3   ,   1   union all
select  46  ,   1   ,   1   union all
select  47  ,   2   ,   1   union all
select  48  ,   3   ,   0   union all
select  49  ,   1   ,   0   union all
select  50  ,   2   ,   0   union all
select  51  ,   3   ,   0   union all
select  52  ,   1   ,   0   union all
select  53  ,   2   ,   1   union all
select  54  ,   3   ,   1   union all
select  55  ,   1   ,   1   union all
select  56  ,   2   ,   1   union all
select  57  ,   3   ,   0   union all
select  58  ,   1   ,   1   union all
select  59  ,   2   ,   1   union all
select  60  ,   3   ,   1   union all
select  61  ,   1   ,   0   union all
select  62  ,   2   ,   0   union all
select  63  ,   3   ,   1   union all
select  64  ,   1   ,   1   union all
select  65  ,   2   ,   1   union all
select  66  ,   3   ,   1   union all
select  67  ,   1   ,   0   union all
select  68  ,   2   ,   0   union all
select  69  ,   3   ,   0   union all
select  70  ,   1   ,   0   union all
select  71  ,   2   ,   0   union all
select  72  ,   3   ,   1   union all
select  73  ,   1   ,   1   union all
select  74  ,   2   ,   1   union all
select  75  ,   3   ,   1   union all
select  76  ,   1   ,   0   union all
select  77  ,   2   ,   1   union all
select  78  ,   3   ,   1   union all
select  79  ,   1   ,   1   union all
select  80  ,   2   ,   0   union all
select  81  ,   3   ,   0   union all
select  82  ,   1   ,   1   union all
select  83  ,   2   ,   1   union all
select  84  ,   3   ,   1   union all
select  85  ,   1   ,   1   union all
select  86  ,   2   ,   0   union all
select  87  ,   3   ,   0   union all
select  88  ,   1   ,   0   union all
select  89  ,   2   ,   0   union all
select  90  ,   3   ,   0   union all
select  91  ,   1   ,   1   union all
select  92  ,   2   ,   1   union all
select  93  ,   3   ,   1   union all
select  94  ,   1   ,   1   union all
select  95  ,   2   ,   0   union all
select  96  ,   3   ,   1   union all
select  97  ,   1   ,   1   union all
select  98  ,   2   ,   1   union all
select  99  ,   3   ,   0   union all
select  100 ,   1   ,   0   union all
select  101 ,   2   ,   1   union all
select  102 ,   3   ,   1   union all
select  103 ,   1   ,   1

So, let's run a simple CTE with the data we have. Then from here show us where we are and what we're trying to achieve:

;With Parent(CustomerID, ParentCustomerID, IsBillToCustomer)
As
(
   Select c.CustomerID, c.ParentCustomerID, c.IsBillToCustomer
    from Customer c
    WHERE c.ParentCustomerID = 0
    UNION ALL
  Select c.CustomerID, c.ParentCustomerID, c.IsBillToCustomer
    from Customer c
    inner join Customer p on p.CustomerID=c.ParentCustomerID
)

Select *
  from Parent p

Help us understand the problem. Thanks.

StackExchange Database Administrators Q#17772, answer score: 2