Почему параметр порядка `` `вызывает у Racket REPL нехватку памяти?

Question

Я вижу проблему при замене порядка параметров на функцию -.

; source 

(define (compose f g) (lambda (x) (f (g x)))) 

(define (repeated f n) 
    (if (= n 1) 
    f 
    (compose f (repeated f (- 1 n))) ; causes an out of memory error 
    (compose f (repeated f (- n 1))) ; runs without issue 
)) 

(define (square n) (* n n)) 
((repeated square 2) 6) ; 1296 


; REPL 

> > Racket virtual machine has run out of memory; aborting 
Aborted (core dumped) 

Проблема стоит, если я жестко задал значение. Кроме того, проблема не применяется, если я увеличиваю n, используя +.

Answer 1

Когда вы начинаете с n, являющегося 2, вы тогда звоните (repeated f (- 1 2)). (- 1 2) - -1, который не равен 1, поэтому он продолжается с (repeated f (- 1 -1)). (- 1 -1) - 2, поэтому вы снова вызываете (repeated f 2), и вы достигли бесконечного цикла.

При использовании другого заказа вы начинаете с (- 2 1), что равно 1, так что рекурсия останавливается.

Другими словами: если вы начинаете с номером больше 1 и вы держите вычитанием 1 от n, вы будете в конечном итоге достичь 1 и рекурсия остановится. Если вы вместо этого вычтите n от 1, вы попадете в цикл, и рекурсия продолжится навсегда (или, вернее, до тех пор, пока у вас не закончится память).

Та же проблема не возникает с добавлением, потому что добавление является коммутативным. Это добавление x к y и добавление y к x дает тот же результат. То же самое не относится к вычитанию.