Is this a recursive or iterative function?
<p>I am using the SICP book which is build for Scheme/Racket (lisp family). In this exercise I had some problems:</p>

<p><em>1.11 A function f is defined by the rule that f(n) = n if n&lt;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.</em></p>

<p>A fully recursive function in Racket for this exercise is easy:</p>

<pre><code> (define (f n) 
    (cond ((&lt; n 3) n) 
         (else (+ (f (- n 1)) 
                  (* 2 (f (- n 2))) 
                  (* 3 (f (- n 3)))))))  
</code></pre>

<p>It is tough to build an iterative one. Since I was not figuring it out, I tried with Python.</p>

<p>When I did it in python, it came out with the following code:</p>

<pre><code>def funcao_f(n):   
    count = 0
    limite = n - 2
    soma = 0
    if n&lt;3:
        return n
    else:
        while count!=limite:
            count = count + 1
            soma = funcao_f(n-1)+2*funcao_f(n-2)+3*funcao_f(n-3)
    return soma
</code></pre>

<p>I am in doubt about the nature of this python code.</p>

<p>Is this a recursive function? </p>

<p>(I called funcao_f inside funcao_f)</p>

<p>Is this an iterative function? </p>

<p>(I am using a while loop inside it)</p>

<p>Does Python accept a process to be both, iterative and recursive?</p>

<p>I think the answer to this question might clear my understanding of the concepts if iteration and recursion. </p>

<p>Note that the question asks about recursive and iterative <em>processes</em>. In scheme, both will be implemented using a recursive <em>function</em> (or <em>procedure</em>, as used in SICP), but the evaluation will be quite different. Please make sure you understand the difference between a recursive function and a recursive process as described in that chapter in SICP. (As scheme has tail-call-optimization, the fact that a procedure is recursive is "the syntactic fact that the procedure refers (either directly or indirectly) to itself" [SICP, 1.2.1])</p>

<p>If you compare with the recursive and iterative fibonacci exmples in the beginning of 1.2.2 Tree recursion, you can come up with a function with an iterative process, like</p>

<pre><code>(define (f n)
  (define (f-iter i n m1 m2 m3)
    (if (= i n)
      (+ m1 (* 2 m2) (* 3 m3))
      (f-iter (+ i 1) n (+ m1 (* 2 m2) (* 3 m3)) m1 m2)))

   (if (&lt; n 3)
     n
     (f-iter 3 n 2 1 0)))
</code></pre>

python recursion iteration racket sicp