This is the code for single integer, how can it extend to arbitrarily large input by passing list as a parameter?
(define (factors n)
(define (*factors d)
(cond ((> d n) (list))
((= (modulo n d) 0) (cons d (*factors (+ d 1))))
(else (*factors (+ d 1)))))
(*factors 1))
(display (factors 1111111))
(newline)
"...how can it extend to arbitrarily large input by passing list as a parameter?"
The process described by the posted *factors
procedure is not iterative, i.e., not tail-recursive, and it will grow stack space for large inputs. I take it that OP is interested in finding a tail-recursive version of this code to improve the space efficiency.
You can convert this to an iterative process by adding an accumulator to the helper procedure. This allows results to be stored in the accumulator and passed through recursive calls without the need for any further operations when those calls return, i.e., tail recursion.
(define (factors-iter n)
(define (iter d result)
(cond ((> d n) (reverse result))
((zero? (modulo n d))
(iter (+ d 1) (cons d result)))
(else
(iter (+ d 1) result))))
(iter 1 '()))
Here are the results of tracing the execution of these procedures:
> (factors-trace 8)
|(%factors 1 8)
| (%factors 2 8)
| |(%factors 3 8)
| |(%factors 4 8)
| | (%factors 5 8)
| | (%factors 6 8)
| | (%factors 7 8)
| | (%factors 8 8)
| | |(%factors 9 8)
| | |()
| | (8)
| |(4 8)
| (2 4 8)
|(1 2 4 8)
(1 2 4 8)
> (factors-iter-trace 8)
|(iter 1 8 ())
|(iter 2 8 (1))
|(iter 3 8 (2 1))
|(iter 4 8 (2 1))
|(iter 5 8 (4 2 1))
|(iter 6 8 (4 2 1))
|(iter 7 8 (4 2 1))
|(iter 8 8 (4 2 1))
|(iter 9 8 (8 4 2 1))
|(1 2 4 8)
(1 2 4 8)
Here factors-trace
and factors-iter-trace
are slightly modified versions of the factors
and factors-iter
definitions, allowing for a trace. You can see that the %factors
process grows in stack size as the computation progresses, but iter
maintains a constant stack size.
As others have already answered, the easiest way to use factors-iter
with a list of inputs is to use map
:
> (map factors-iter '(4 42 314 2998))
((1 2 4) (1 2 3 6 7 14 21 42) (1 2 157 314) (1 2 1499 2998))