77043

Tail-Recursive Power Function in Scheme

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.

Answer1:

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)))))

Answer2:

Even though it has the same name, it's not the same parameter. If you dug into what the interpreter is doing you'll see "a" defined twice. Once for the local scope, but it still remembers the "a" on the outer scope. When the interpreter invokes a function it tries to bind the values of the arguments to the formal parameters.

The reason that you pass the values through rather mutating state like you would likely do in an algol family language is that by not mutating state you can use a substitution model to reason about the behaviour of procedures. That same procedure called at anytime with arguments will yeild the same result as it is called from anywhere else with the same arguments.

In a purely functional style values never change, rather you keep calling the function with new values. The compiler should be able to write code in a tight loop that updates the values in place on the stack (tail call elimination). This way you can worry more about the correctness of the algorithm rather than acting as a human compiler, which truth be told is a very inefficient machine-task pairing.

Recommend

  • How to escape colon (:) character while executing native SQL queries against an Informix database us
  • How do I check if System::Collections:ArrayList is empty / nullptr / null?
  • Creating a C++ function that calls other Lua function
  • INSERT EXEC Statement cannot be nested [duplicate]
  • Get used tables from sql query [duplicate]
  • How to use function wrapper in mustache.php?
  • In matplotlib, how do you change the fontsize of a single figure?
  • JSR-330 support in Picocontainer : @Inject … @Named(\"xxx)
  • How Get arguments value using inline assembly in C without Glibc?
  • Creating a DropDownList
  • Spring: No transaction manager has been configured
  • How to make R's read_csv2() recognise the text characters properly
  • Who propagate bugfixes across branches (corporate development)?
  • pillow imaging ImportError
  • accepts_nested_attributes_for practical form use for in Rails 3
  • Web.config system.webserver errors
  • Object and struct member access and address offset calculation
  • Implementation of State Monad
  • Why Encoding.ASCII != ASCIIEncoding.Default in C#?
  • one Local Olampyad Questions on Informatic in 2011
  • How do I pass the string value parameter of the selected list item from an auto-populated dropdown l
  • Exception “firebase.functions() takes … no argument …” when specifying a region for a Cloud Function
  • Highlight one bar in a series in highcharts?
  • Scrapy recursive link crawler
  • Sony Xperia Z Tablet not found by adb
  • How to recover from a Spring Social ExpiredAuthorizationException
  • Statically linking a C++ library to a C# process using CLI or any other way
  • How can I estimate amount of memory left with calling System.gc()?
  • Function pointer “assignment from incompatible pointer type” only when using vararg ellipsis
  • R: gsub and capture
  • Calling of Constructors in a Java
  • 0x202A in filename: Why?
  • jqPlot EnhancedLegendRenderer plugin does not toggle series for Pie charts
  • Comma separated Values
  • PHP: When would you need the self:: keyword?
  • KeystoneJS: Relationships in Admin UI not updating
  • Hits per day in Google Big Query
  • File not found error Google Drive API
  • Net Present Value in Excel for Grouped Recurring CF
  • How to load view controller without button in storyboard?