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)))))))
count = 0
limite = n - 2
soma = 0
count = count + 1
soma = funcao_f(n-1)+2*funcao_f(n-2)+3*funcao_f(n-3)
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.