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>Adapting an iterative fibonacci answer</p>

<p><a href="http://stackoverflow.com/a/15047141/901925">http://stackoverflow.com/a/15047141/901925</a></p>

<pre><code>def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a
</code></pre>

<p>This problem is:</p>

<pre><code>def far(n):
    a,b,c=0,1,2
    for _ in range(n):
        a,b,c = b, c, a+b+c 
    return a # ,b,c
</code></pre>

<p>The recursive code is:</p>

<pre><code>def foo(n):
    if n&lt;3: return n
    return foo(n-1)+foo(n-2)+foo(n-3)
</code></pre>

<p>and testing:</p>

<pre><code>In [814]: for i in range(10):
     ...:     print(foo(i), far(i))
     ...:     
0 0
1 1
2 2
3 3
6 6
11 11
20 20
37 37
68 68
125 125
</code></pre>

<p>The iterative version is significantly faster, especially as numbers grow (20 and above).</p>

python recursion iteration racket sicp