1.2

Linear Recursion and Iteration

; first method
; Recursive process = expansion occurs as the process builds up a chain of deferred operations, contraction occurs as the operations are performed

(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

; second method
;  iterative process is a repetitive algorithmic approach where a sequence of instructions is repeatedly executed, typically within a loop, until a certain condition is met or a desired result is achieved.

(define (factorial n)
    (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count)))

(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

NOTE :

There is a difference between a recursive process and a recursive procedure.

When a procedure is descibed as recursive, we are referring to the syntactic fact that the procedure refers to itself in its definition.

When a process is described as recursive, we are refering to the way the process evolves through deferred operations

fact-iter is a recursive procedure but an iterative process.

Recursion thought process

base case + greedy solution

def add(a,b):
  if a>b:
    return 0
  return a + add(a+1,b)

"""
add(2,5)
= 2 + add(3,5)
= a + add(a+1,b)
"""