Pedro Delfino - 8 months ago 71

Python Question

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.

Answer

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.

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
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.