<PAGE>

                                                                  Exhibit 4.1(a)

                           RECAPITALIZATION AGREEMENT

      This Recapitalization Agreement (the "Agreement") is made and entered into
as the 31st day of October, 1999, by and between Rural Cellular Corporation, a
Minnesota corporation (including its successors, assigns and subsidiaries,
"RCC") and Telephone & Data Systems, Inc., a Delaware corporation (including its
successors, assigns and subsidiaries, "TDS").

                                R E C I T A L S:

      A.    TDS presently owns (directly and indirectly) within the meaning of
            the FCC Cross-Ownership Rule (defined below), five hundred
            eighty-six thousand seven hundred ninety-nine (586,799) shares of
            RCC's Class A Common Stock, par value $.01 per share (the "Class A
            Common Stock") and one hundred thirty-two thousand five hundred
            ninety-seven (132,597) shares of RCC's Class B Common Stock, par
            value $.01 per share (the "Class B Common Stock"); and

      B.    TDS has an ownership interest in RCC through its ownership of the
            Class A Common Stock and Class B Common Stock identified in Recital
            A above and has an ownership interest through its subsidiary, United
            States Cellular Corporation, in licenses in cellular channel blocks
            in rural service areas OR-3 and OR-6; and

      C.    RCC is presently negotiating with Triton Cellular Partners, L.P.,
            for the acquisition (the "Triton Acquisition") of FCC licenses and
            related assets for the "A" frequency channel blocks, in, among other
            rural service areas OR-3 and OR-6 (the "A" frequency channel blocks
            in OR-3 and OR-6 are hereinafter referred to as the "Oregon
            Competing Channel Blocks"); and

      D.    Pursuant to the Cross-Ownership Rule (defined below), the
            acquisition by RCC of the FCC licenses for the Oregon Competing
            Channel Blocks would be permissible under the Cross-Ownership Rule
            only if TDS's ownership interest in RCC does not exceed five percent
            (5%), with respect to each class of RCC's equity securities
            outstanding; and

      E.    As of the date hereof TDS's ownership of Class A Common Stock and
            Class B Common Stock exceeds the five percent limitation provided in
            the Cross-Ownership Rule; and

      F.    TDS's ownership of Class A Common Stock and Class B Common Stock in
            excess of the five percent limitation provided in the
            Cross-Ownership Rule limits the opportunities of RCC and TDS to
            acquire FCC licenses and related assets for certain channel blocks
            in cellular markets where the other already controls or operates the
            competing channel block for such cellular market (the "Cross
            Ownership Issues"); and

<PAGE>

      G.    Remediating the Cross-Ownership Issues generally will also remediate
            Cross-Ownership Issues with respect to RCC's possible acquisition of
            the Oregon Competing Channel Blocks in connection with the Triton
            Acquisition; and

      H.    RCC and TDS desire to consummate a transaction to remediate the
            Cross-Ownership Issues generally, and specifically with regard to
            the Triton Acquisition (i) if acceptable to the FCC in remediation
            of Cross-Ownership Issues, through the exchange of the Excess Shares
            (defined below) for RCC's convertible preferred stock pursuant to a
            tax free recapitalization in accordance with the provisions of
            Section 368(a)(1)(E), 354, 351(g) and other applicable provisions of
            the Internal Revenue Code of 1986, as amended (the "FCC
            Recapitalization"); or (ii) alternatively, in the event that the
            transaction described in (i) of this Recital H is not acceptable to
            the FCC in remediation of Cross-Ownership Issues, through the
            issuance of a convertible subordinated debenture in exchange for the
            Excess Shares, but only if RCC acquires the contract right to
            acquire the FCC licenses and related assets for the "A" frequency
            channel blocks in rural service areas OR-3 and OR-6 in the Triton
            Acquisition (the "Triton Recapitalization"); and

      I.    RCC and TDS desire to enter into this Agreement pursuant to which,
            under the terms and conditions set forth herein, RCC and TDS will
            consummate a transaction to remediate the Cross-Ownership Issues.

                                   AGREEMENT:

      NOW, THEREFORE, in consideration of the foregoing premises, the mutual
covenants contained herein and for other good and valuable consideration, the
receipt and sufficiency of which are hereby acknowledged, the parties do hereby
agree as follows:

                                    ARTICLE 1
                                   DEFINITIONS

      For purposes of this Agreement, the following terms shall have the
meanings set forth below:

      "Acquisition Agreement" means that certain Asset Purchase Agreement in
executable form between Triton Cellular Partners, L.P., a Delaware limited
partnership, designated wholly owned subsidiaries of Triton Cellular Partners,
L.P., defined as the "Triton Entities" (collectively defined as the "Triton
Parties") and RCC, subject to such amendments as are negotiated by the Triton
Parties and RCC prior to execution thereof.

      "Class A Common Stock" has the meaning set forth in the Recitals;

      "Class B Common Stock" has the meaning set forth in the Recitals;

      "Closing" has the meanings given in Section 9.1;

      "Code" means the Internal Revenue Code of 1986, as amended, and the
Treasury Regulations promulgated thereunder;


                                       2
<PAGE>

      "Convertible Preferred Stock" means shares of RCC's convertible preferred
stock issued by RCC containing the terms and conditions set forth on the term
sheet attached hereto as Exhibit A, to be delivered by RCC to TDS on the FCC
Closing Date in accordance with the provisions of this Agreement;

      "Cross-Ownership Issues" has the meaning given in the Recitals.

      "Cross-Ownership Rule" means Subpart H of Part 22 of Title 47 of the Code
of Federal Regulations, Section 22.942 entitled "Limitations on interest in
licensees for both channel blocks in an area" as amended September 22, 1999,
scheduled to become effective November 6, 1999.

      "Debenture" means a convertible subordinated debenture issued by RCC
containing the terms and conditions set forth on the term sheet attached hereto
as Exhibit B, to be delivered by RCC to TDS on the Triton Closing Date in
accordance with the provisions of this Agreement.

      "Excess Shares" means the aggregate number of whole (not fractional)
shares of Class A Common Stock and Class B Common Stock which are in excess of
five percent (5%) of the issued and outstanding shares of each respective class
of RCC common stock, determined as of the Closing Date; the calculation of the
aggregate number of said shares being made in accordance with the applicable
provisions of the Cross-Ownership Rule to reduce TDS's ownership interest in RCC
such that TDS shall have a direct or indirect ownership interest in RCC of not
more than five percent (5%) in accordance with Section 22.942(a) thereof.

      "FCC" means the Federal Communications Commission.

      "FCC Closing" means the closing of the FCC Recapitalization.

      "FCC Closing Date" means the date on which the FCC Closing shall occur.

      "FCC Recapitalization" has the meaning set forth in the recitals.

      "Oregon Competing Channel Blocks" has the meaning given in the Recitals.

      "Owned Entity" means any entity in which TDS or RCC , as applicable, has
an "ownership interest" as that term is used in subsection (d)(7) of the
Cross-Ownership Rule.

      "Purchase Price" has the meaning set forth in Section 3.1.

      "RCC" has the meaning set forth in the preamble.

      "RCC Price" means $50 5/8 per Excess Share, which takes into consideration
the size of the block of shares, the low "float", and the recent volatility of
the market in RCC shares.

      "Section 4.1 Payment" has the meaning set forth in Section 4.1.

      "TDS" has the meaning set forth in the preamble.

      "Triton Acquisition" has the meaning set forth in the recitals.


                                       3
<PAGE>

      "Triton Closing" means the closing of the Triton Recapitalization.

      "Triton Closing Date" means the date on which the Triton Closing shall
occur.

      "Triton Recapitalization" means the transactions contemplated by Article 3
and Article 4 of this Agreement, consummated on the terms and conditions set
forth herein.

                                    ARTICLE 2
                              FCC RECAPITALIZATION

      2.1 FCC Authorization to Proceed with Preferred Stock Recapitalization.
Notwithstanding any other provision of this Agreement to the contrary, the
parties shall consummate the transactions contemplated by this Agreement in the
form of the FCC Recapitalization if the issuance of Convertible Preferred Stock
by RCC to TDS on the terms set forth in Exhibit A is acceptable to the FCC to
remedy the existence of Cross-Ownership Issues generally, including any Cross
Ownership Issue with respect to RCC's possible acquisition of the Oregon
Competing Channel Blocks. It shall be conclusive to the parties that the
issuance of Convertible Preferred Stock by RCC to TDS on the terms set forth in
Exhibit A is acceptable to remedy such Cross-Ownership Issues (a) if the FCC
shall provide a written opinion stating its acceptance of such remedy, or (b) if
the FCC shall grant an application of RCC or TDS for the transfer of control or
the assignment of a cellular license in circumstances where a Cross-Ownership
Issue exists and such application expressly sets forth the issuance of
Convertible Preferred Stock by RCC to TDS on the terms set forth in Exhibit A as
a remedy of such Cross-Ownership Issue.

      2.2 Exchange of Excess Shares for Preferred Stock. In the event parties
proceed with the FCC Recapitalization, on the FCC Closing Date RCC shall issue
Convertible Preferred Stock to TDS in exchange for the surrender by TDS of the
Excess Shares. The number of shares of Convertible Preferred Stock so delivered
to TDS on the FCC Closing Date shall be determined by multiplying the total
number of Excess Shares by the RCC Price and dividing the dollar amount so
determined by one thousand dollars ( fractional shares shall be permitted ).

      2.3 Other Terms. In the event that the parties proceed with the FCC
Recapitalization, the provisions of Articles 3 and 4 shall not apply. All other
sections of this Agreement shall be applicable without any additional
considerations.

      2.4 Tax Characterization. RCC and TDS shall treat the Convertible
Preferred Stock as equity for United States federal, state and local income tax
purposes and to take no position inconsistent with such characterization on any
tax return.

                                    ARTICLE 3
                             TRITON RECAPITALIZATION

      Except as provided in Article 2, on the Triton Closing Date, RCC agrees to
purchase the Excess Shares from TDS and TDS agrees to sell, assign, transfer and
deliver the Excess Shares to RCC, on the terms and conditions set forth below:


                                       4
<PAGE>

      3.1 Purchase Price. The "Purchase Price" for the Excess Shares shall be
the amount determined by multiplying the total number of Excess Shares by the
RCC Price.

      3.2 Payment of Purchase Price. In the event the parties proceed with the
Triton Recapitalization, on the Triton Closing Date RCC shall issue to TDS the
Debenture in exchange for the surrender by TDS of the Excess Shares .The face
value of the Debenture to be so delivered to TDS on the Triton Closing Date
shall be equal to the Purchase Price (fractional issuance shall be permitted).

                                    ARTICLE 4
                 ADDITIONAL COVENANTS TO TRITON RECAPITALIZATION

      In the event that RCC purchases the Excess Shares pursuant to Article 3,
the following provisions shall apply:

      4.1 RCC shall pay to TDS on the Closing Date the Section 4.1 Payment.
"Section 4.1 Payment" means an amount determined under the following formula:

      Gain x TR/(1-TR)

where Gain means the excess of the fair market value of the Excess Shares on the
Closing Date over TDS's tax basis in the Excess Shares, and TR means 0.4. For
example, if the fair market value of the Excess Shares on the Closing Date was
$20 million and TDS's tax basis in the Excess Shares was $5 million, the Section
4.1 Payment would be equal to $10 million ($15 million Gain x 0.4/0.6). For
purposes of the foregoing calculation, the fair market value of the Excess
Shares on the Closing Date shall be assumed to be equal to the Purchase Price;
provided, however, that if, as a result of an audit or examination of TDS or any
of its subsidiaries, a taxing authority asserts that the fair market value of
the Excess Shares on the Closing Date exceeded the Purchase Price, the Section
4.1 Payment shall be redetermined accordingly and RCC shall pay to TDS the
difference between the revised Section 4.1 Payment and the originally determined
Section 4.1 Payment together with any interest and penalties resulting from such
redetermination and contest expenses relating thereto. RCC shall be given prompt
notice of any such audit and an opportunity to participate (at its own expense)
in the resolution of any issues that would affect it but only to the extent such
issue can be separated on audit from any other tax issues of TDS. TDS shall
vigorously contest any recharacterizations of the payments hereunder and payment
shall be due from RCC only after a final non-appealable determination with
respect thereto or a further contest becomes commercially unreasonable. For
purposes of the foregoing calculation, the Excess Shares shall constitute those
shares of the Class A Common Stock and Class B Common Stock owned by TDS which
have the highest tax basis, thereby resulting in the lowest taxable income to
TDS.

      4.2 If at any time within five years following the Closing, TDS or any of
its subsidiaries sells or otherwise disposes of any of its shares of Class A
Common Stock or Class B Common Stock owned as of the Closing Date (excluding the
Excess Shares) in a taxable transaction, TDS will refund to RCC, in conjunction
with such sale, a portion of the Section 4.1 Payment in an amount equal to the
Section 4.1 Payment multiplied by a fraction, the numerator of which is the
number of shares of RCC stock sold or otherwise disposed of and the


                                       5
<PAGE>

denominator of which is the total number of Excess Shares; provided, however,
that in no event shall the aggregate amount refunded pursuant to this Section
4.2 exceed the Section 4.1 Payment.

                                    ARTICLE 5
                         FCC CROSS-OWNERSHIP COMPLIANCE

      5.1 TDS Cross-Ownership Compliance. From the date of this Agreement until
(i) the earlier of the FCC Closing Date, the Triton Closing Date or the
termination of this Agreement, and (ii) if either the FCC Closing or the Triton
Closing occurs, then perpetually thereafter, TDS shall not take any action , or
cause any of its subsidiaries or Owned Entities to take any action, that will
result in TDS, any of its subsidiaries or any of its Owned Entities to be in
non-compliance with the Cross-Ownership Rule as applicable to competing channel
blocks for cellular markets that TDS and RCC may control or operate. The
preceding sentence shall not preclude any action taken subject to FCC approval
of such action (e.g., signing a transaction agreement which requires FCC
approval of the contemplated transaction as a condition precedent to the closing
of such transaction) or subject to coming into compliance with the
Cross-Ownership Rule (e.g. divestiture of one or more markets that cause the
non-compliance with the Cross-Ownership Rule).

      In the event that TDS or its subsidiaries do acquire any additional
ownership interest in RCC, whether or not caused by TDS, TDS agrees that it will
promptly take such commercially reasonable action as it determines to be
necessary to cause the resulting non -compliance with the Cross Ownership Rule
as applicable to competing channel blocks for cellular markets that TDS and RCC
may control or operate to be remedied.

      5.2 RCC Cross-Ownership Compliance. From the date this Agreement until (i)
the earlier of the FCC Closing Date, the Triton Closing Date or the termination
of this Agreement, and (ii) if either the FCC Closing or the Triton Closing
occurs, then perpetually thereafter, RCC shall not take any action , or cause
any of its subsidiaries or Owned Entities to take any action, that will result
in RCC, any of its subsidiaries or any of its Owned Entities to be in
non-compliance with the Cross-Ownership Rule as applicable to competing channel
blocks for cellular markets that TDS and RCC may control or operate. The
preceding sentence shall not preclude any action taken subject to FCC approval
of such action (e.g., signing a transaction agreement which requires FCC
approval of the contemplated transaction as a condition precedent to the closing
of such transaction) or subject to coming into compliance with the
Cross-Ownership Rule (e.g. divestiture of one or more markets that cause the
non-compliance with the Cross-Ownership Rule).

                                    ARTICLE 6
     CONDITIONS PRECEDENT TO PARTIES OBLIGATIONS TO TRITON RECAPITALIZATION

      In the event that RCC consummates a transaction pursuant to the
Acquisition Agreement which does not include the Oregon Competing Channel
Blocks, or any other cellular license which would create the existence of a
cross-ownership interest prohibited by the Cross-


                                       6
<PAGE>

Ownership Rule, neither RCC nor TDS shall be obligated to consummate the Triton
Recapitalization.

                                    ARTICLE 7
                      REPRESENTATIONS AND WARRANTIES OF RCC

      As an inducement for TDS to enter into this Agreement and consummate the
transactions contemplated hereby, intending that TDS rely thereon in entering
into and performing this Agreement, RCC warrants and represents to TDS the
following:

      7.1 Due Authorization. The execution, delivery and performance of this
Agreement, including the Convertible Preferred Stock, the Debenture and the
other documents, instruments and agreements to be executed and/or delivered by
RCC pursuant to this Agreement, and the consummation of the transactions
contemplated hereby and thereby have been duly and validly authorized by all
necessary corporate action on the part of RCC.

      7.2 Valid Issuance. At the FCC Closing or the Triton Closing, as
applicable, RCC will deliver to TDS the Convertible Preferred Stock or the
Debenture, as applicable, and such securities of RCC will be legally binding,
validly issued and fully paid, securities of RCC enforceable against RCC in
accordance with their terms and applicable law.

                                    ARTICLE 8
                      REPRESENTATIONS AND WARRANTIES OF TDS

        As an inducement for RCC to enter into this Agreement and consummate the
transactions contemplated hereby, intending that RCC rely thereon in entering
into and performing this Agreement, TDS warrants and represents to RCC the
following:

      8.1 Due Authorization. The execution, delivery and performance of this
Agreement, including the documents, instruments and agreements to be executed
and/or delivered by TDS pursuant to this Agreement, and the consummation of the
transactions contemplated hereby and thereby have been duly and validly
authorized by all necessary corporate action on the part of TDS.

      8.2 Clear Title. At the FCC Closing or the Triton Closing, as applicable,
TDS will convey to RCC title to the Excess Shares free and clear of any and all
liens, claims and encumbrances of any kind, nature or description whatsoever.

                                    ARTICLE 9
                          CLOSING; ADDITIONAL COVENANTS

      9.1 Closing Date. The closing of the transaction contemplated by this
Agreement (the "Closing") shall be effected by the delivery of such documents
and instruments as are contemplated by this Agreement as of the FCC Closing Date
or the Triton Closing Date, as applicable. The FCC Closing Date shall be the
date established for the FCC Closing by written notice given by RCC to TDS, or
by TDS to RCC, but in no event shall such FCC Closing Date be less than ten
business days after receipt of such notice by the receiving party. The Triton
Closing Date shall be the "Closing Date" of the Acquisition Agreement, and shall
be established


                                       7
<PAGE>

by written notice given by RCC to TDS, but in no event shall such Triton Closing
Date be less than four business days after receipt of such notice by TDS.

      9.2 Pre-Closing. Three business days prior to the anticipated FCC Closing
Date or Triton Closing Date, as applicable, ("Pre-Closing Date"), TDS and RCC
shall each execute and deliver to an escrow agent which shall be mutually
acceptable to RCC and TDS their respective closing documents described in
Section 9.4, which documents and instruments shall be held in escrow pending the
Closing.

      9.3 Effective Time. The Closing of the transaction contemplated by this
Agreement shall be effective as of the beginning of business on the FCC Closing
Date or Triton Closing Date, as applicable. In the event the transactions
contemplated by the Acquisition Agreement are not consummated within ten
business days following the Pre-Closing Date, then the escrow shall be
terminated and the closing documents executed by each respective party shall be
returned thereto, but such event shall not result in a termination of this
Agreement except as expressly provided in Section 10.11 hereof.

      9.4 Closing Documents.

            (a) Documents to be Delivered by TDS. At the Closing, TDS shall
      execute, where necessary or appropriate, and deliver to RCC the
      certificates evidencing the Excess Shares duly endorsed in blank or
      accompanied by Assignments Separate from Certificate duly executed in
      blank.

            (b) Documents to be Delivered by RCC. At the Closing, RCC shall
      execute, where necessary or appropriate, and deliver to TDS each and all
      of the following:

                  (i)   The Convertible Preferred Stock, if the transaction is
                        consummated in accordance with the provisions of Article
                        2; or a Debenture in the amount of the Purchase Price,
                        duly endorsed by an authorized officer of RCC if the
                        transaction is consummated in accordance with the
                        provisions of Article 3.

                  (ii)  If the transaction is consummated by issuing the
                        Debenture, a cash payment delivered by wire transfer of
                        immediately available funds to an account or accounts
                        designated by TDS in an amount equal to the Section 4.1
                        Payment.

                  (iii) A copy certified by the Secretary of RCC of the duly
                        adopted resolutions of the Board of Directors of RCC
                        approving this Agreement and authorizing the execution
                        and delivery of this Agreement, including the
                        Convertible Preferred Stock or Debenture, as applicable,
                        and other documents, instruments and agreements to be
                        executed and/or delivered by RCC pursuant hereto, and
                        the consummation of the transactions contemplated hereby
                        and thereby.


                                       8
<PAGE>

                                   ARTICLE 10
                                  MISCELLANEOUS

      10.1 Further Acts and Assurances. Each party will, at any time from time
to time, on and after the FCC Closing or the Triton Closing, as applicable, upon
reasonable request of the other party, do all such further acts and things and
execute, acknowledge and deliver, or cause to be executed, acknowledged and
delivered, any and all papers, documents, instruments, agreements, deeds,
assignments, transfers, assurances and conveyances as may be necessary or
desirable carryout and give effect to the provisions of this Agreement and (a)
with respect to further acts by TDS, to vest, perfect and confirm of record in
RCC, its successors and assigns, title to the Excess Shares, and (b) with
respect to further acts by RCC, to vest, perfect and confirm of record in TDS,
it successors and assigns, title to the Convertible Preferred Stock or the
Debenture, as applicable.

      10.2 Entire Agreement. This Agreement, including the documents,
instruments and agreements to be executed by the parties pursuant hereto,
contains the entire agreement of the parties hereto and supersedes all prior or
contemporaneous agreements and understandings, oral or written between the
parties hereto with respect to the subject matter hereof.

      10.3 Specific Performance. Each party acknowledges that the other party
will have no adequate remedy at law if it shall fail to perform any of its
obligations hereunder, and (a) with respect to TDS's possible failure to
perform, including but not limited to surrendering the Excess Shares in
accordance with this Agreement, and (b) with respect to RCC's possible failure
to perform, including but not limited to, the issuance of Convertible Preferred
Stock in accordance with Article 2 or the issuance of the Debenture in
accordance with Article 3. In such event, each party shall have the right, in
addition to any other rights it may have, to specific performance of this
Agreement.

      10.4 Amendments. No purported amendment, modification or waiver of any
provision of this Agreement or any of the documents, instruments or agreements
to be executed by the parties pursuant hereto shall be effective unless in a
writing specifically referring to this Agreement and signed by both parties.

      10.5 Notices. All notices or other communications hereunder shall be in
writing and shall be given (and shall be deemed to have been given upon receipt)
by delivery in person against receipt by overnight courier service, by facsimile
transmission, or by registered or certified mail (return receipt requested and
postage prepaid) with an acknowledgement of receipt signed by the addressee or
authorized representative thereof, addressed as follows (or to such other
address for a party as shall be specified by like notice):

      If to TDS:          Telephone & Data Systems, Inc.
                          30 North LaSalle Street
                          Chicago, Illinois  60602
                          Attn: LeRoy T. Carlson, Chairman


                                       9
<PAGE>

      With a copy to:     Sidley & Austin
                          Bank One Plaza
                          10 South Dearborn
                          Chicago, Illinois 60603
                          Attention: William S. DeCarlo, Esq.

      If to RCC:          Rural Cellular Corporation
                          3905 Dakota Street S.W.
                          Alexandria, MN  56308
                          Attn: Ann K. Newhall, Esq.

      With a copy to:     Moss & Barnett
                          A Professional Association
                          4800 Norwest Center
                          90 South Seventh Street
                          Minneapolis, MN  55402-4129
                          Attn:  Richard J. Kelber, Esq.

      10.6 Successors and Assigns. This Agreement shall be binding upon and
inure to the benefit of the parties hereto and the respective successors and
permitted assigns, but nothing in this Agreement is to be construed as an
authorization or right of any party to assign its rights or delegate its duties
under this Agreement without the prior written consent of the other party
hereto.

      10.7 Costs. RCC shall pay its own costs and expenses and promptly
reimburse TDS for its costs and expenses incurred in connection with negotiating
and preparing this Agreement and consummating the transactions contemplated
hereby (including the consummation of the Closing of the exchange of the Excess
Shares for the Convertible Preferred Stock or the Debenture, as applicable, and
the consummation of the closing of the conversion of the Convertible Preferred
Stock or Debenture for Class A Common Stock or Class B Common Stock, as
applicable), including but not limited to fees and disbursements of their
attorneys and accountants.

      10.8 Counterparts; Facsimile Signatures. This Agreement may be executed in
two or more counterparts, each of which shall be deemed an original but all of
which together shall constitute one and the same agreement. Facsimile signatures
on this Agreement shall be deemed to be original signatures.

      10.9 Severability. In the event that any provision of this Agreement is
declared or held by any court of competent jurisdiction to be invalid or
unenforceable, such provision shall be severable from, and such invalidity or
unenforceablity shall not be construed to have any effect on, the remaining
provisions of this Agreement, unless such invalid or unenforceable provision
goes to the essence of this Agreement, in which case the entire Agreement may be
declared invalid and not binding upon any of the parties.


                                       10
<PAGE>

      10.10 Incorporation of Recitals. The Recitals set forth above are
incorporate in this Agreement as if fully set forth herein and shall constitute
an expression of the intent of the parties and shall act as an aid in the
construction of this Agreement.

      10.11 Termination. This Agreement may be terminated (i) at any time, by
the mutual written agreement of the parties; or (ii) upon thirty (30) days prior
written notice by either party if neither the FCC Closing nor the Triton Closing
shall have occurred on or before the first anniversary of this Agreement.

      10.12 Applicable Law. This Agreement shall be governed by and construed in
accordance with the laws of the State of Minnesota without giving effect to the
conflicts of laws principles thereof and without regard to any rules of
construction or interpretation as to which party drafted this Agreement.

      10.13 Confidentiality of Agreement and Acquisition Agreement. Each party
shall keep secret and retain in strictest confidence, and shall not, without the
express prior written consent of an executive officer of the other party,
directly or indirectly disclose the terms, conditions or existence of this
Agreement (and TDS shall also keep secret and retain in strict confidence the
Acquisition Agreement, including the negotiations and transaction contemplated
thereby) except, with respect to this Agreement, to: (i) its representatives,
and, with respect to RCC, to Triton Cellular Partners, L.P. and its
representatives (who shall be informed of the confidential nature of such
information and who shall agree to keep such information confidential); (ii) the
FCC, subject to Section 10.16; and (iii) as otherwise required by applicable
law, including securities or communications laws. In the event a party breaches,
or threatens to commit a breach, of the provisions of this Section 10.13, the
non-breaching party or non-threatening party, as applicable, shall have the
right, in addition to any other rights and remedies available to such
non-breaching or non-threatening party, as applicable, at law or in equity, to
equitable relief, including injunctions, against such breach or threatened
breach, it being acknowledged and agreed that any such breach or threatened
breach will cause irreparable harm to such non-breaching or non-threatening
party, as applicable, and that money damages would not be an adequate remedy to
such non-breaching or non-threatening party, as applicable.

      10.14 Alternative Transaction. Following the date hereof and continuing
thereafter until the Pre-Closing Date or the termination of this Agreement prior
to the Pre-Closing Date by mutual agreement, TDS and RCC will work together in
good faith to determine an alternative approach to consummating the transactions
contemplated by the Triton Recapitalization, the purpose being to develop, if
possible, the terms and conditions of a transaction in remediation of
Cross-Ownership Issues with respect to the Oregon Competing Channel Blocks which
will mitigate, to the maximum extent possible, the Section 4.1 Payment which
would result from consummating the Triton Recapitalization, and if a mutually
agreeable alternative approach is so determined, to amend this Agreement, as
appropriate, to incorporate the terms of such alternative approach and to
implement that approach as soon as practicable.

      10.15 Arbitration. The parties intend this Agreement to be a legally
binding agreement. If any term of this Agreement is unclear or incomplete and
the parties cannot resolve the issue through negotiation expeditiously, the
parties shall resolve their differences as to the interpretation hereof by
arbitration pursuant to the rules of the American Arbitration Association,


                                       11
<PAGE>

held in Minneapolis, Minnesota . The arbitrator shall be a practicing attorney
specializing in corporate finance or a certified public accountant , in each
case with at least twenty years of experience.

      10.16 Redaction. This Agreement shall not be filed with the FCC without
first being redacted to eliminate references to Triton or its property, direct
or indirect, or by which it might be identified.

      10.17 Reasonable Efforts. The parties agree to use all commercially
reasonable efforts to put this Agreement into effect expeditiously, including
preparation of documents, application to the FCC for a ruling, and all other
necessary actions.

                                   ARTICLE 11

                             NON-DILUTION PROVISION

      11.1 Non -Dilution Provision. As a holder of the Convertible Preferred
Stock or the Debenture, as applicable, TDS's right as a holder of such
securities to convert the same into Class A Common Stock or Class B Common
Stock, as applicable, shall be protected from dilution under the circumstances
and in the manner set forth in the following sentences (the "Non-Dilution
Provision"):

      In the event that, at any time after the exchange of the Excess Shares and
      prior to the conversion of the Convertible Preferred Stock or the
      Debenture, as applicable, RCC shall effect (i) a dividend upon its Class A
      Common Stock or its Class B Common Stock payable in its Class A Common
      Stock or its Class B Common Stock or other property other than cash,
      including common stock, preferred stock or other securities of a
      subsidiary corporation, (ii) a combination of its outstanding Class A
      Common Stock or its Class B Common Stock into a smaller number of such
      Class A Common Stock or Class B Common Stock, (iii) a subdivision of its
      outstanding Class A Common Stock or Class B Common Stock into a larger
      number of such Class A Common Stock or Class B Common Stock or (iv) any
      reorganization or reclassification of its Class A Common Stock or Class B
      Common Stock, or any liquidation, consolidation or merger with another
      corporation, or the sale of all or substantially all of its assets to
      another corporation, in such a way that the holders of its outstanding
      Class A Common Stock or Class B Common Stock shall be entitled to receive
      (either directly, or upon subsequent liquidation) stock, securities or
      other property (including cash) with respect to or in exchange for such
      Class A Common Stock or Class B Common Stock, (any such event set forth in
      (i) - (iv) above referred to as a "Diluting Event"), then as a condition
      of such Diluting Event lawful and adequate provisions shall be made
      whereby TDS shall be entitled to receive, (under the same terms otherwise
      applicable to TDS' receipt of RCC's Class A Common Stock or Class B Common
      Stock) upon TDS' conversion of the Convertible Preferred Stock or the
      Debenture, as applicable, (the "RCC Convertible Shares"), the following:
      (i) if the Diluting Event results in an exchange of RCC's Class A Common
      Stock or its Class B Common Stock for other property, TDS shall be
      entitled to receive in lieu of the RCC Convertible Shares to which TDS was
      entitled immediately prior to the Diluting Event but which TDS had not yet
      received, such shares of stock, securities or other property as may be
      issued or payable by virtue of the Diluting Event in exchange for that
      number of


                                       12
<PAGE>

      RCC Convertible Shares to which TDS was entitled immediately prior to the
      Diluting Event but which it had not yet received; (ii) if the Diluting
      Event results in an issuance or payment with respect to RCC's Class A
      Common Stock or its Class B Common Stock, TDS shall be entitled to
      receive, in addition to the RCC Convertible Shares to which it was
      entitled immediately prior to the Diluting Event but which it had not yet
      received, such shares of stock, securities or other property as may be
      issued or payable by virtue of the Diluting Event with respect to that
      number of RCC Convertible Shares to which TDS was entitled immediately
      prior to the Diluting Event but which it had not yet received. If any
      Diluting Event occurs, provision shall be made with respect to TDS' rights
      and interests resulting from the application of this Section to ensure
      that this Section applies as well to any shares of stock, securities or
      other property deliverable to TDS as a result of such Diluting Event.

      IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be
executed by duly authorized representatives as of the day, month and year first
above-written.

                                       RURAL CELLULAR CORPORATION


                                       By   /s/ Richard P. Ekstrand
                                       Its   President


                                       TELEPHONE & DATA SYSTEMS, INC.


                                       By   /s/ LeRoy T. Carlson
                                       Its   Chairman




            Signature Page to Recapitalization Agreement relating to
             Telephone & Data System's Inc.'s Ownership Interest in
                Rural Cellular Corporation dated October 31, 1999


<PAGE>


                                AMENDED EXHIBIT A

                   TERM SHEET FOR CONVERTIBLE PREFERRED STOCK

o     Class: The convertible preferred stock shall be a separate class of
      preferred stock. Only TDS, affiliates of TDS or TDS Owned Entities or
      their respective successors and assigns shall hold such separate class of
      preferred stock.

o     Date of Issuance: Issuance of the convertible preferred stock shall be
      conditioned upon the FCC's acceptance of the issuance of such convertible
      preferred stock as a remedy for the Cross-Ownership Issues (the "FCC
      Closing Date").

o     Liquidation Preference: The convertible preferred stock shall have a
      liquidation preference of $1,000.00 per share.

o     Amount: The Excess Shares shall be exchangeable for convertible preferred
      stock based on a ratio determined by dividing the product of $50 5/8 (the
      RCC common stock price as of October 22, 1999 ) times the number of Excess
      Shares by $1,000.00.

o     Term: The preferred stock is mandatorily redeemable by the Company for
      cash on the first day following the twentieth ( 20th ) anniversary of the
      date of issuance.

o     Payment of Dividends: Dividends on the convertible preferred stock shall
      be cumulative, with a fixed coupon rate of four percent (4%) per annum.
      Dividends would be payable at the end of the term , at which point they
      would be declared and paid unless prohibited by law . In the event of
      conversion prior to the end of the term , dividends would not be declared
      . The convertible preferred stock will also participate on a current basis
      in dividends, if any, declared with respect to the Company's Class A
      Common Stock or Class B Common Stock.

o     Conversion: The convertible preferred stock shall convert in the aggregate
      into the same number of shares of Class A and Class B Common Stock as the
      number of Excess Shares originally exchanged. Partial conversions shall be
      effected on a proportionate basis. The Non-Dilution Provision shall apply.
      The convertible preferred stock shall be convertible at any time prior to
      the twentieth ( 20th ) anniversary at the option of either TDS or the
      Company, in whole or in part, so long as the issuance of shares of the
      Company's Class A Common Stock and/or Class B Common Stock shall not
      violate the then applicable FCC rules on cross-ownership.

o     Subordination: The convertible preferred stock shall be subordinate, at
      the option of the Company as exercised from time to time , to any or all
      classes of preferred stock and debt, whether now outstanding or hereafter
      issued, with respect to the liquidation preference and the payment of
      dividends.

o     Transferability: The convertible preferred stock shall be transferable by
      TDS to the extent permitted under applicable securities laws, provided
      that notice of any proposed

<PAGE>

      transfer must be provided to the Company at least 30 days in advance and,
      if the Company so requires, an opinion of counsel satisfactory to the
      Company that such transfer does not violate the registration requirements
      of federal or state securities laws, and, further provided, that such
      transfer shall not be in violation of any FCC rule nor result in a Cross
      Ownership Issue between RCC and the transferee . To the extent that any
      shares of convertible preferred stock which are convertible into Class B
      Common Stock are transferred to a person that is not an affiliate of TDS
      (as the term "affiliate" is defined in RCC's Articles of Incorporation,)
      such share(s) of convertible preferred stock transferred shall thereafter
      be convertible only into Class A Common Stock. The conversion rights will
      not be transferable separate from the convertible preferred stock.

o     Registration Rights: The convertible preferred stock shall not be
      registered under federal or state securities laws.

 (See also the First Amendment with regard to a potential "Additional Dividend")


                                       2
<PAGE>

                                    EXHIBIT B

               TERM SHEET FOR SUBORDINATED CONVERTIBLE DEBENTURES

o     Date of Issuance: Issuance of the convertible debentures shall be
      conditioned upon and concurrent with the closing of the Acquisition
      Agreement (the "Triton Closing Date").

o     Amount: The dollar amount of the subordinated convertible debenture shall
      be determined as of the Triton Closing Date and shall equal the number of
      shares to be redeemed in exchange for the debenture times the RCC Price.

o     Term: The debenture will mature on the first day after the twentieth
      (20th) anniversary of the date of issuance.

o     Interest Rate: Interest shall accrue at the Applicable Federal Rate (as
      defined in the Internal Revenue Code and regulations) for long-term
      instruments, fixed as of the Closing Date (the "Interest Rate").

o     Payment of Interest: Interest shall be payable, at the Company's option,
      either in cash or by issuance of additional subordinated convertible
      debentures ("PIK") in an amount equal to the dollar amount of the interest
      due. With respect to any interest payment due the holder payable in PIK,
      the holder shall be paid an "Additional Amount of Interest" on the
      principal in accordance with the following formula:

            (Interest Rate X .4 X .09) / .6

      For example, if the Interest Rate is 6.39%, the Additional Amount of
      Interest would be .383%, determined as follows: (6.39% X .4 X .09) / .6 =
      .383%

o     Conversion. The debenture shall be convertible, in the aggregate, into the
      same number of shares of Class A Common Stock and Class B Common Stock, as
      the number of Excess Shares originally exchanged therefor; provided,
      however, that if any interest payment due the holder was not paid in cash,
      the holder shall be entitled upon conversion to an additional number of
      shares of Class A Common Stock and Class B Common Stock, as applicable, in
      an amount equal to Additional Amount of Interest X $1,000 per $1,000
      amount of debenture (under the above example, $3.83 / $1,000) for each
      year the debenture was outstanding and interest was not paid in cash. For
      purposes of determining such additional number of shares of Class A Common
      Stock and Class B Common Stock, as applicable, such applicable dollar
      amount shall be divided by the average closing price of Class A Common
      Stock for the five trading days immediately prior to the conversion date.
      Partial conversions shall be effected on a proportionate basis. The
      Non-Dilution Provision shall apply. The debentures shall be convertible at
      any time at the option of either TDS or the Company, in whole or in part,
      so long as the issuance of the shares shall not violate the then
      applicable FCC rules on cross-ownership.

<PAGE>

o     Subordination: The debentures shall be deeply subordinated to all classes
      of preferred stock and debt of RCC, whether now or hereafter issued, with
      respect to the liquidation preference and payment of interest.

o     Transferability: The debentures shall be transferable by TDS to the extent
      permitted under applicable securities laws, provided that notice of any
      proposed transfer must be provided to the Company at least 30 days in
      advance and, if the Company so requires, an opinion of counsel
      satisfactory to the Company that such transfer does not violate the
      registration requirements of federal or state securities laws, and,
      further provided, that such transfer shall not be in violation of any FCC
      rule nor result in a Cross Ownership Issue between RCC and the transferee.
      To the extent that any debenture is transferred to a person that is not an
      affiliate of TDS (as the term "affiliate" is defined in RCC's Articles of
      Incorporation), such debenture shall thereafter be convertible only into
      Class A Common Stock. The conversion rights will not be transferable
      separate from the debentures.

o     Registration Rights: The debentures shall not be registered under federal
      or state securities laws. No registration rights shall attach to the
      debentures.