While doing exercise 1.12 from Structure and Interpretation of Computer Programs, I needed to learn an interesting technique for recursion. How does one write a nested loop in functional programming, i.e. recursively?
For example, consider this 2-dimensional loop:
#!/usr/bin/python3
for y in range(20):
for x in range(y + 1):
print('{:3} '.format(x * y), end='')
print()
How would this loop look in Scheme? Think of the problem in these steps:
- You will only write one function. (You don’t need to write a function for
every
for
loop.) - Every looping variable, along with any other state that changes along the course of the operation, must become a parameter to the function.
- Every
for
loop becomes anif
statement which helps the function determine where it is in the process.
This is the final product in Scheme:
#!/usr/bin/guile
!#
(use-modules (ice-9 format))
(define (show n-rows x y)
; This first condition detects whether we are at the end of the entire
; operation.
(when (< y n-rows)
; Check to see if we're at the end of a row.
(if (> x y)
; Reset x and increment y.
(begin
(newline)
(show n-rows 0 (1+ y)))
; If the condition was false, do the stuff in the innermost loop.
(begin
(format #t "~3d " (* x y))
; Increment x. y stays the same, because it's the outer loop
; variable.
(show n-rows (1+ x) y)))))
; Start x and y at 0.
(show 20 0 0)
The output of both programs should be identical.