方案中的尾递归幂函数 [英] Tail-Recursive Power Function in Scheme

问题描述

我在编写一个尾递归功能函数时遇到了麻烦。我想用辅助函数编写函数。我知道我需要一个参数来保存一个累计值，但之后我就陷入了困境。我的代码如下。

 （define（pow-tr ab）
（define（pow-tr-h result）
 （如果（= b 0）
结果
 pow-tr a（ -  b 1））（* result a））pow-tr-h 1）
  

我编辑了我的代码，现在可以使用了。如下所示：

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $（定义（pow-tr2-hab结果）
（if（= 0 b）
result
（pow-tr2-ha（ - b 1）（* result a））））
（pow-tr2-hab 1））

有人可以向我解释为什么辅助函数应该具有与主函数相同的参数。我很难想出为什么这是必要的。

解决方案

声明辅助函数应该具有与主函数相同的参数是不正确的。您只需在每次迭代中传递要更改的参数 - 例如，指数和累计结果。例如，如果没有传递基类作为参数，这将工作正常：

 （define（pow-tr2 ab）
（定义（pow-tr2-hb结果）
（如果（= b 0）
结果
（pow-tr2-h（ -  b 1）（* result a）））） 
（pow-tr2-hb 1））
  

它可以工作，因为内部辅助程序可以查看外部主程序中定义的 a 参数。而且由于基地永远不会改变，我们不必传递它。要了解更多信息，请参阅精彩的 SICP 书。

现在你使用的是辅助程序，它会是开始使用命名为 let ，这是一种非常方便的编写帮助程序的语法，无需显式编码内部过程。上面的代码相当于这个：

 （define（pow-tr2 ab）
（let pow-tr2- （b）（结果1）] 
（如果（= b 0）
结果
（pow-tr2-h（ -  b 1）（* result a））））） 
  

I am having trouble writing a tail-recursive power function in scheme. I want to write the function using a helper function. I know that I need to have a parameter to hold an accumulated value, but I am stuck after that. My code is as follows.

(define (pow-tr a b)
(define (pow-tr-h result)
  (if (= b 0)
     result
     pow-tr a (- b 1))(* result a)) pow-tr-h 1)

I edited my code, and now it works. It is as follows:

(define (pow-tr2 a b)
 (define (pow-tr2-h a b result)
  (if (= 0 b)
    result
    (pow-tr2-h a (- b 1) (* result a))))
 (pow-tr2-h a b 1))

Can someone explain to me why the helper function should have the same parameters as the main function. I am having a hard time trying to think of why this is necessary.

解决方案

It's not correct to state that "the helper function should have the same parameters as the main function". You only need to pass the parameters that are going to change in each iteration - in the example, the exponent and the accumulated result. For instance, this will work fine without passing the base as a parameter:

(define (pow-tr2 a b)
  (define (pow-tr2-h b result)
    (if (= b 0)
        result
        (pow-tr2-h (- b 1) (* result a))))
  (pow-tr2-h b 1))

It works because the inner, helper procedure can "see" the a parameter defined in the outer, main procedure. And because the base is never going to change, we don't have to pass it around. To read more about this, take a look at the section titled "Internal definitions and block structure" in the wonderful SICP book.

Now that you're using helper procedures, it'd be a good idea to start using named let, a very handy syntax for writing helpers without explicitly coding an inner procedure. The above code is equivalent to this:

(define (pow-tr2 a b)
  (let pow-tr2-h [(b b) (result 1)]
    (if (= b 0)
        result
        (pow-tr2-h (- b 1) (* result a)))))

这篇关于方案中的尾递归幂函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！