recursionschemeiterationsicp# No idea how to solve SICP exercise 1.11

A function

`f`

is defined by the rule that`f(n) = n`

if`n < 3`

and`f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)`

if`n > 3`

. Write a procedure that computes`f`

by means of a recursive process. Write a procedure that computes`f`

by means of an iterative process.

Implementing it recursively is simple enough. But I couldn't figure out how to do it iteratively. I tried comparing with the Fibonacci example given, but I didn't know how to use it as an analogy. So I gave up (shame on me) and Googled for an explanation, and I found this:

```
(define (f n)
(if (< n 3)
n
(f-iter 2 1 0 n)))
(define (f-iter a b c count)
(if (< count 3)
a
(f-iter (+ a (* 2 b) (* 3 c))
a
b
(- count 1))))
```

After reading it, I understand the code and how it works. But what I don't understand is the process needed to get from the recursive definition of the function to this. I don't get how the code could have formed in someone's head.

Could you explain the thought process needed to arrive at the solution?

Solution

You need to capture the state in some accumulators and update the state at each iteration.

If you have experience in an imperative language, imagine writing a while loop and tracking information in variables during each iteration of the loop. What variables would you need? How would you update them? That's exactly what you have to do to make an iterative (tail-recursive) set of calls in Scheme.

In other words, it might help to start thinking of this as a while loop instead of a recursive definition. Eventually you'll be fluent enough with recursive -> iterative transformations that you won't need to extra help to get started.

For this particular example, you have to look closely at the three function calls, because it's not immediately clear how to represent them. However, here's the likely thought process: (in Python pseudo-code to emphasise the imperativeness)

Each recursive step keeps track of three things:

```
f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)
```

So I need three pieces of state to track the current, the last and the penultimate values of `f`

. (that is, `f(n-1), f(n-2) and f(n-3)`

.) Call them `a, b, c`

. I have to update these pieces inside each loop:

```
for _ in 2..n:
a = NEWVALUE
b = a
c = b
return a
```

So what's NEWVALUE? Well, now that we have representations of `f(n-1), f(n-2) and f(n-3)`

, it's just the recursive equation:

```
for _ in 2..n:
a = a + 2 * b + 3 * c
b = a
c = b
return a
```

Now all that's left is to figure out the initial values of `a, b and c`

. But that's easy, since we know that `f(n) = n if n < 3`

.

```
if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
a = a + 2 * b + 3 * c
b = a
c = b
return a
```

That's still a little different from the Scheme iterative version, but I hope you can see the thought process now.

- SQL Server recursive query in a CTE issue
- Why <slot item={child} /> is needed for the nested object to be displayed if <slot item={item} /> is present?
- How to loop over a multidimensional objectArray with Smarty?
- TypeScript recursive union function type
- Time complexity for recursive binary search that also prints current subarray
- How can I fix an error the error `Cannot build rewrite system for generic signature; rule length limit exceeded` in swift?
- Find the parent element of an array by the id of its child
- recursion on nested list need some support
- How do you prove termination of a recursive list length?
- python recursion i dont understand this output pls help me
- Why does recursively running `joblib.Parallel` increases the computation time?
- I'm trying to understand recursion in Tcl, but every time the recursion finishes it throws errors
- How to remove all numbers from a list in Lisp
- Calculate the total weight of segments
- Why does the expression !(cin>>word) cause infinite recursion?
- What's the best way to recursively traverse a BinaryTree in Java without void methods?
- can anybody explains the code and also recursion tree
- Is it possible to limit the depth of a recursive directory listing in S3 bucket?
- takeWhile implementation in JavaScript - Looking for better ideas
- I used a recursive function to modify a string, but if the string is too large the function returns nothing
- How to Compress Paths in SQL Server Using Recursive CTE with Node Visibility Conditions?
- Why this recursion example in ocaml doesn't work for negative number?
- Recursive loop on a list to print xml with indent
- Big O of algorithm that steps over array recursively
- Powerset of a list with equal elements in Java
- Recursion in FP-Growth Algorithm
- Passing list to function results in no case clause matching
- Convert tree-like structure formatted as a string using indentations to a list of paths
- Recursive function fails depending on lexical scoping
- Creating a list of interleaved elements: Prolog