view raw
Pedro Delfino Pedro Delfino - 8 months ago 71
Python Question

Is this a recursive or iterative function?

I am using the SICP book which is build for Scheme/Racket (lisp family). In this exercise I had some problems:

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

A fully recursive function in Racket for this exercise is easy:

(define (f n)
(cond ((< n 3) n)
(else (+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3)))))))

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

When I did it in python, it came out with the following code:

def funcao_f(n):
count = 0
limite = n - 2
soma = 0
if n<3:
return n
while count!=limite:
count = count + 1
soma = funcao_f(n-1)+2*funcao_f(n-2)+3*funcao_f(n-3)
return soma

I am in doubt about the nature of this python code.

Is this a recursive function?

(I called funcao_f inside funcao_f)

Is this an iterative function?

(I am using a while loop inside it)

Does Python accept a process to be both, iterative and recursive?

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


Your funcao_f function is recursive.

The definition of recursive function can be: f is recursive if it calls f directly or indirectly, eg.:

def f(x):
    if x <= 0:
        return 0
        return g(x)

def g(y):
    return 5 + f(x - 1)

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

Your lisp function:

(define (f n) 
    (cond ((< n 3) n) 
         (else (+ (f (- n 1)) 
              (* 2 (f (- n 2))) 
              (* 3 (f (- n 3)))))))

Could be translated in Python like this:

def f(n):
    if n < 3:
        return n
        return f(n - 1) + 2 * f(n - 2) + 3 * f(n - 3)

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