Pedro Delfino - 1 year ago 156
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
else:
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
else:
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.

``````(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
else:
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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download