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>Your <code>funcao_f</code> function is recursive.</p>

<p>The definition of <strong>recursive</strong> function can be:
<em>f</em> is recursive if it calls <em>f</em> directly or indirectly, eg.:</p>

<pre><code>def f(x):
    if x &lt;= 0:
        return 0
    else:
        return g(x)

def g(y):
    return 5 + f(x - 1)
</code></pre>

<p>The definition of <strong>iterative</strong> function is not so easy to write. I think we could define it like this: <em>f</em> is iterative if it is not recursive.</p>

<p>Your lisp function:</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>Could be translated in Python like this:</p>

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

<p>To convert this function to an iterative function, you need 3 local variable to keep the values of <em>f</em> for <em>n</em> - 1, <em>n</em> - 2 and <em>n</em> - 3. And use a loop, of course.</p>

python recursion iteration racket sicp