Translating SICP solution from Scheme to Python

Question

I have this solution for SICP code in Lisp:

 ;; ex 1.11. Iterative implementation 

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

I don't really know how Lisp works; I understand a few thing here, but it's still hard for me to translate it to Python. For example, I don't know why a is written below if. How could this code be translated to Python or C++? (the function have to be iterative and not recursive)

Answer 1

There are two ways to think about the translation. One would be to write a literal, straight translation without respecting Python's idioms and conventions - it will look like this:

def f(n):
    def iter(a, b, c, count):
        if count == 0:
            return a
        else:
            return iter(b, c, 2*b + 3*a + c, count-1)
    return iter(0, 1, 2, n)

The other way is to write the code in a Pythonic fashion such that it respects the target language's conventions and makes use of its iteration mechanisms:

def f(n):
    a, b, c = 0, 1, 2
    for count in range(n):
        a, b, c = b, c, 2*b + 3*a + c
    return a

By the way, the second version will be faster, and won't have a problem with an stack overflow error (Python is not optimized for recursion!). It's irrelevant that in the recursive version count goes from n to 0 and in the loop version count goes from 0 to n, because anyway the value of count is not being used for anything besides iterating a given number of times.