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>The function that you reported is a recursive function.</p>

<p>The Wikipedia <em>Recursion</em> page sentences:</p>

<blockquote>
  <p>Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).</p>
</blockquote>

<p>Usually, in a recursive algorithm you have to provide:</p>

<ol>
<li>the base case, when your recursion will end and</li>
<li>the recursion call/step.</li>
</ol>

<p>In your function the base case is:</p>

<pre><code>if n&lt;3:
  return n
</code></pre>

<p>and the recursive step is contained in the <em>else</em> branch:</p>

<pre><code>soma = funcao_f(n-1)+2*funcao_f(n-2)+3*funcao_f(n-3)
</code></pre>

<p>In fact, in the recursive step you are splitting the problem in three sub-problems as suggested by the definition that I have cited at the beginning of the answer.</p>

python recursion iteration racket sicp