mit-scheme-users
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Understanding the difference betwee `subproblem level` and `reduction nu


From: Francesco Ariis
Subject: Understanding the difference betwee `subproblem level` and `reduction number`
Date: Mon, 17 Oct 2022 13:07:55 +0200

Hello schemers,
    I am not getting the difference between `subproblem level` and
`reduction number`. Relevant manual chapter:

    
https://www.gnu.org/software/mit-scheme/documentation/stable/mit-scheme-user/Subproblems-and-Reductions.html

The explanation starts from:

    (define (factorial n)
      (if (< n 2)
        1
        (* n (factorial (- n 1)))))

and says that if we somehow stop the computation while evaluating
`(- n 1)`:

    (- n 1)                       is subproblem level 0
    (factorial (- n 1)))))        is subproblem level 1
    (* n (factorial …)            is subproblem level 2

Everything is clear here.

But then it goes on to say that if we go further up , the `if` expression
is not at subproblem level 3 (as I would have guessed), but at
“reduction number” 1.

Indeed if I `(debug)` and then `B` to the `if` expression, I get:

    Subproblem level: 2  Reduction number: 1

It is not clear to me what the difference is between “levels” and
“reduction numbers” is or if that matters debugging-wise.

Thanks in advance
—F




reply via email to

[Prev in Thread] Current Thread [Next in Thread]