How does Scheme return the “built up” value of a recursive procedure after the base case is met?

0
votes

I'm going through Simply Scheme and just got to the section on recursion.

I don't understand why when the base case is met Scheme returns the "built up" value of the recursive procedure and not the actual argument value which caused the base case to evaluate to #t.

For example, have a look at this sample code snippet of a recursive procedure which takes a word as input, reverses it, and spits it back out:

(define (reverse wd)
  (if (empty? wd) wd
      (word (last wd) (reverse (bl wd)))))

Here's what confuses me: (if (empty? wd) wd

I understand that when the actual argument value for the formal parameter wd is empty (or "") the base case evaluates to #t, causing the value of the second argument to if to be evaluated.

What I don't understand is how the second argument to if (wd, in this case) can return something that's not empty even though it would appear to be the same, empty, formal parameter that triggered the base case.

What am I missing?

If there's something in the documentation (or the text) which explains this I'd be happy to review it.

2
recursionschememit-scheme
Just to be clear (and it may already be clear), the value of (if test then-part else-part) is then-part if test is true, and else-part if test is false. So whenever wd is empty, you are returning wd (which is empty). Whenever wd is not empty, though, you're returning (word (last wd) (reverse (bl wd))). Do you see why that won't be empty when wd isn't empty? Even without considering (reverse (bl wd)), and just looking at (word (last wd) …) we see something non-empty since (last wd) is something and (word <something> …) is a string beginning with <something>. - Joshua Taylor
@JoshuaTaylor - yes, I understand. Sylwester and Chris Jester-Young helped suss out the final point in below comments. Your contributions would be welcome. - d3vin

2 Answers

2
votes

Since state doesn't change here you could just substitute what the function does with its recursion. Imagine you have a two letter word a :

(reverse a) ; =>
(word (last a) (reverse (bl a))) ; ==>
(word (last a) (word (last (bl a)) (reverse (bl (bl a))))) ; ==>
(word (last a) (word (last (bl a)) (bl (bl a)))) ; ==>
(word (last a) (word (last (bl a)) '()))

The last (bl (bl a)) is the only thing done by the last iteration and it's '(). The rest is done as the continuation of the previous calls.

EDIT

To clarify.. Imagine a is "ab"

(reverse "ab") ; turns into
(word (last "ab") (reverse (bl "ab")))           ; tuns into
(word "b" (reverse (bl "ab")))                   ; turns into 
(word "b" (reverse "a")))                        ; turns into 
(word "b" (word (last "a") (reverse (bl "a"))))) ; turns into
(word "b" (word "a" (reverse ""))))

Now look at that last one.. When (reverse "") returns "" it's the result used in the previous form call, in the word form, so you'll get (word "a" "") ==> "a", then that will be returned to the first call that does (word "b" "a"). These are continuations.

1
votes

The key insight is that it is returning empty for the base case. That's because the reverse of an empty string is an empty string.

The recursive cases actually work on that assumption. In words, here's how your reverse function works:

  1. If the given word is empty, return empty.
  2. Otherwise, take the last letter from the word, and join that with the reverse of the remainder of the word.

Example. Let's say we're reversing "Devin":

  • The word "Devin" isn't empty, so we will join "n" with the reverse of "Devi".
    • The word "Devi" isn't empty, so we will join "i" with the reverse of "Dev".
      • The word "Dev" isn't empty, so we will join "v" with the reverse of "De".
        • The word "De" isn't empty, so we will join "e" with the reverse of "D".
          • The word "D" isn't empty, so we will join "D" with the reverse of "".
            • The word "" is empty, so we return "".
          • Here, we return "D" joined with "", which is "D".
        • Here, we return "e" joined with "D", which is "eD".
      • Here, we return "v" joined with "eD", which is "veD".
    • Here, we return "i" joined with "veD", which is "iveD".
  • Here, we return "n" joined with "iveD", which is "niveD".