Headline

An extra paramter for an intermediate result in recursive functions

Illustration

Consider the following recursive formulation of the Factorial function in Language:Java.

public static long factorial(int n) {
  if (n<=1) 
    return 1;
  else 
    return n*factorial(n-1);
}

While perfectly valid as a function definiton, the particular form of recursion, i.e., primitive recursion rather than tail recursion may be a source of ineffeciency. That is, the call stack grows with each recursive call, even though this would be easily avoidable, for example, with a non-recursive forumulation. There is also a more efficient, tail-recursive formulation, which uses an extra parameter to pass on the product computed by the function.

public static long factorial(int n) {
  return factorial(1, n);
}
public static long factorial(int r, int n) {
  if (n<=1) 
    return r;
  else 
    return factorial(n*r, n-1);
}

More generally, the idea is to move the computations for post-processing results into the extra argument position.

Metadata


There are no revisions for this page.

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.