Question

a. An infinite continued fraction is an expression of the form $$ f=\frac{N_{1}}{D_{1}+\frac{N_{2}}{D_{2}+\frac{N_{3}}{D_{3}+\cdots}}} $$ As an example, one can show that the infinite continued fraction expansion with the \(N_{i}\) and the \(D_{i}\) all equal to 1 produces \(1 / \phi\), where \(\phi\) is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation-a so-called \(k\)-term finite continued fraction - has the form $$ \frac{N_{1}}{D_{1}+\frac{N_{2}}{\ddots+\frac{N_{K}}{D_{K}}}} $$ Suppose that \(\mathrm{n}\) and \(\mathrm{d}\) are procedures of one argument (the term index \(i\) ) that return the \(N_{i}\) and \(D_{i}\) of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont- frac \(\mathrm{n} \mathrm{d} \mathrm{k}\) ) computes the value of the \(k\)-term finite continued fraction. Check your procedure by approximating \(1 / \phi\) using \(\begin{aligned} \text { (cont-frac (lambda (i) } & 1.0 \text { ) } \\ &\text { (lambda (i) } 1.0) \\ & \text { k) } \end{aligned}\) for successive values of \(\mathrm{k}\). How large must you make \(\mathrm{k}\) in order to get an approximation that is accurate to 4 decimal places? b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Short answer

k = 10 is needed for accuracy to 4 decimal places.

Step-by-step solution

Understanding the Problem

We need to create a procedure `cont-frac` that evaluates a k-term finite continued fraction. The functions `n(i)` and `d(i)` provide the numerators and denominators for each term. Specifically, for approximating \(1/\phi\), we will use the simplest continued fraction where each term's numerator and denominator are both 1. Our goal is to determine how large \( k \) should be to approximate \(1/\phi\) accurate to 4 decimal places.

Defining the Recursive Procedure

To define a recursive process for the continued fraction, we construct the structure by iteratively applying substitutions. For a continued fraction of depth k, the computation unfolds as follows: ``` (define (cont-frac n d k) (define (recursion i) (if (> i k) 0 (/ (n i) (+ (d i) (recursion (+ i 1)))))) (recursion 1)) ``` This procedure `recursion` computes the continued fraction starting at the bottom where terms beyond `k` contribute nothing (i.e., they evaluate to 0), working upward.

Verifying and Testing the Recursive Procedure

Invoke the procedure to approximate \( \frac{1}{\phi} \) using:```(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k)```Test for successive values of \(k\) until it reaches the accuracy of 4 decimal places. Approximate values are checked against \( \frac{1}{\phi} \). Start with \(k = 1, 2, 3, \ldots\) and increase until the result stabilizes sufficiently close to 0.6180, which is approximate \(\frac{1}{\phi}\).

Determining Minimum k for Accuracy

Upon testing the recursive function with different values of \(k\), it is found that when \(k = 10\), the approximation stabilizes to 0.6180 to 4 decimal places. This suggests \(k = 10\) is sufficient for the desired accuracy.

Developing the Iterative Process

To switch the process to iterative, avoid recursion by keeping track of intermediate results: ``` (define (cont-frac n d k) (define (iter i result) (if (= i 0) result (iter (- i 1) (/ (n i) (+ (d i) result))))) (iter k 0)) ``` This `iter` function starts with a base result of 0 and accumulates the value while decrementing the index.

Key concepts

Recursive Algorithms

Recursive algorithms are techniques where a function calls itself as a part of its computation. In the case of evaluating a continued fraction using recursion, the idea is simple. You start from the term at the deepest point and then progress upwards, reusing the function with a smaller subproblem each time.
It is a powerful method but can run into issues if depths become too large since each recursive call adds a layer that takes memory.

The provided example from the exercise uses a recursive method for the continued fraction where the function continues to call itself with a decreasing value of the index until it hits zero:

• Each call calculates the next step by dividing the numerator by the sum of the denominator and the recursive call of the next fraction.
• When the index exceeds the depth `k`, it returns zero, acting as a base case to halt further function calls.

To effectively use recursive algorithms:

• Ensure you have a clear base case to stop further recursion.
• Aim to break the problem into simpler sub-problems solvable through recursion.

In a practical sense, recursion is elegant and often easier to implement, but watch out for depth limitations which could lead to performance issues in computationally extensive scenarios.

Iterative Algorithms

Unlike recursion, iterative algorithms rely on repetitive structures, such as loops, to solve a problem. The example iterative process in the solution uses a loop-like mechanism that accumulates results instead of making additional function calls.
This approach stores results as it proceeds through iterations, which is more memory-efficient versus recursive stacking.

• Start with an initial result, often zero.
• In each iteration, update the result by computing the fraction component and adjusting the index.
• The process stops once the designated number of terms, `k`, have been calculated.

Iterative algorithms are more straightforward when aiming for efficiency.

• They handle larger and/or infinitely expansive tasks well due to their controlled memory use, maintaining simplicity in resource consumption.
• Ensure control structures like loops have a clear exit condition to avoid infinite cycles.

Often, iterative solutions closely resemble the controlled, step-by-step ways one might manually calculate or verify an arithmetic problem. Notably, they are a great option when you want manageable, predictable performance.

Mathematical Approximations

Mathematical approximations involve finding a value that is close to a desired exact figure but simpler to calculate.
In continued fractions, direct calculation of an infinite form is impractical. Instead, truncating the fraction to a finite number of terms makes computation feasible.

• Choose a practical level of truncation that provides the required precision without excessive computation.
• The approximation improves as the number of terms `k` increases, better mimicking the behavior of infinite series.

In the case of calculating an approximation of the golden ratio's reciprocal, using a test that checks progress towards a correct value confirms the adequacy of the chosen depth `k`. Therefore, you:

• Begin with smaller values of `k`, progressively increasing until the result meets a specific precision, such as four decimal places.
• Consider external checks or known values (like the golden ratio's reciprocal) as benchmarks to decide how precise your calculation needs to be.

Approximations balance precision with practicality, allowing complex expressions to be workable and useful in real-world computations. This balance is crucial in fields like engineering, physics, and computer science.