Tail Call - Example Programs

Example Programs

Take this Scheme program as an example:

;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))

This program is not written in a tail recursion style. Now take this Scheme program as an example:

;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (let fact ( ) (if (zero? i) acc (fact (- i 1) (* acc i)))))

The inner procedure fact calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this:

call factorial (3) call fact (3 1) call fact (2 3) call fact (1 6) call fact (0 6) return 6 return 6 return 6 return 6 return 6

into the more efficient variant, in terms of both space and time:

call factorial (3) call fact (3 1) replace arguments with (2 3), jump to "fact" replace arguments with (1 6), jump to "fact" replace arguments with (0 6), jump to "fact" return 6 return 6

This reorganization saves space because no state except for the calling function's address needs to be saved, either on the stack or on the heap, and the call stack frame for fact is reused for the intermediate results storage. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. It is also worth noting, in typical implementations, the tail recursive variant will be substantially faster than the other variant, but only by a constant factor.

Some programmers working in functional languages will rewrite recursive code to be tail-recursive so they can take advantage of this feature. This often requires addition of an "accumulator" argument (acc in the above example) to the function. In some cases (such as filtering lists) and in some languages, full tail recursion may require a function that was previously purely functional to be written such that it mutates references stored in other variables.

An example in pseudo-C follows. Suppose we have the following functions:

int a(int x, int y) { foobar(x, y); return b(x + 1, y + 2); } int b(int u, int v) { foobar(u, v); return u + v; }

Function a can be changed to:

int a(int x, int y) { foobar(x, y); b:u = a:x + 1; b:v = a:y + 2; jump b; }

There are possible aliasing problems but this is the basic idea.

Read more about this topic:  Tail Call

Other articles related to "programs, example programs, program":

Zee Punjabi - Programs - Show Details
... Excuse Me Please is one of the oldest shows of this channel ... Its title song has been sung by popular playback singer Harshdeep Kaur ...
University Of Toronto Scarborough - Academics
... The cooperative education programs, which place students for up to three semesters in workplaces pertaining to their field of study, are unique to the ... Joint programs with Centennial College, that award both a university degree and a college diploma, are offered in journalism, new media, paramedicine ... Four departments of the campus contain programs that award a Bachelor of Arts degree ...
Mouse (programming Language) - Details - Example Programs
... This short program prints 'Hello world.' "Hello world." $ This program displays the squares of the integers from 1 to 10 ...
Upper Canada College - Extracurricular Activities - Programs
... landfill waste and water consumption, and implemented a program of purchasing renewable resources for renovations ...
University Of Alabama
... UA offers programs of study in 13 academic divisions leading to bachelor's, master's, Education Specialist, and doctoral degrees ... Other academic programs unavailable elsewhere in Alabama include doctoral programs in anthropology, library and information studies, metallurgical engineering, music, Romance languages, and social ... The University of Alabama varsity football program (nicknamed the Crimson Tide), which began in 1892, is one the most successful programs in history ...

Famous quotes containing the word programs:

    There is a delicate balance of putting yourself last and not being a doormat and thinking of yourself first and not coming off as selfish, arrogant, or bossy. We spend the majority of our lives attempting to perfect this balance. When we are successful, we have many close, healthy relationships. When we are unsuccessful, we suffer the natural consequences of damaged and sometimes broken relationships. Children are just beginning their journey on this important life lesson.
    —Cindy L. Teachey. “Building Lifelong Relationships—School Age Programs at Work,” Child Care Exchange (January 1994)

    [The Republicans] offer ... a detailed agenda for national renewal.... [On] reducing illegitimacy ... the state will use ... funds for programs to reduce out-of-wedlock pregnancies, to promote adoption, to establish and operate children’s group homes, to establish and operate residential group homes for unwed mothers, or for any purpose the state deems appropriate. None of the taxpayer funds may be used for abortion services or abortion counseling.
    Newt Gingrich (b. 1943)