[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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Understanding the difference betwee `subproblem level` and `reduction number`,
Francesco Ariis <=
- Prev by Date:
Shell
- Previous by thread:
Shell
- Index(es):