Binomial coefficient computation: recursion or iteration? PDF

Preview

Summary

Binomial Coefficient Computation: Recursion or Iteration? Yannis Manolopoulos Data Engineering Laboratory Department of Informatics, Aristotle University Thessaloniki, 54006 Greece [email protected] ABSTRACT all these methods and try to show how we an improve by Binomial oeÆ ient omputation...

Description

Accelerat ing t he world's research.

Binomial coefficient computation: recursion or iteration? Yannis Manolopoulos ACM SIGCSE Bulletin

Cite this paper

Downloaded from Academia.edu 

Get the citation in MLA, APA, or Chicago styles

Related papers

Download a PDF Pack of t he best relat ed papers 

Views of formal program development Eerke Boit en Ab init io met hods for elect ron correlat ion in molecules Mart in Schüt z Dat aflow analysis of array and scalar references Paul Feaut rier

Binomial Coefficient Computation: Recursion or Iteration? Yannis Manolopoulos Data Engineering Laboratory Department of Informatics, Aristotle University Thessaloniki, 54006 Greece

[email protected] ABSTRACT Binomial oeÆ ient omputation, i.e. the al ulation of the number of ombinations of n obje ts taken k at a time, C(n,k), an be performed either by using re ursion or by iteration. Here, we elaborate on a previous report [6℄, whi h presented re ursive methods on binomial oeÆ ient al ulation and propose alternative eÆ ient iterative methods for this purpose.

1.

INTRODUCTION

Re ursion vs. iteration is a topi on whi h students have to be exposed in several ourses, like Computer Programming, Algorithms and Data Stru tures et . When omparing the advantages and disadvantages of re ursion against iteration, we mention the simpli ity in writing and understanding a re ursive program (espe ially if it based on a re ursive mathemati al fun tion), but on the other hand, we emphasize the fa t that re ursive programs are not as eÆ ient as iterative ones, due to the extra time ost for fun tion

alls and extra spa e ost for sta k bookkeeping. Thus, the epilogue in su h a le ture is that if we need to simply have a orre t program, then we an use re ursion; however, if time is a riti al issue, then we have to use iteration. Motivation of the present report is the arti le of Timothy Rolfe in the June 2001 issue of Inroads [6℄, where a number of tips for eÆ ient al ulation of binomial oeÆ ients by using re ursion were examined. Basi ally, the author presented a re urren e relation based on the Pas al triangle, then he derived a more eÆ ient re urren e relation by using some algebra and binomial oeÆ ient properties, and nally he suggested using the greatest ommon divisor to further improve the latter method.

2.

ITERATIVE APPROACHES

When le turing on re ursion and re ursive programs, at the same time we spend quite some time to ompare with equivalent iterative programs. Moreover, we omment on

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ACM SIGCSE Bulletin InRoads, Vol.34, No.4, December 2002. Copyright 2002 ACM X-XXXXX-XX-X/XX/XX ...$5.00.

all these methods and try to show how we an improve by elaborating gradually ea h method. Thus, students apitalize from this engineering approa h. In this respe t, lassi al are the books by Bentley [1, 2, 3℄. For spe i examples that build on su h a progressive approa h, see Se tion 5.3 on Minimum Spanning Trees in the book by Moret and Shapiro [5℄), or Column 7 on the Maximum Subsequen e Problem in [2℄. Several examples an be used for su h a purpose in the

lassroom. For instan e, the al ulation of powers, fa torials, greatest ommon divisors and Fibona

i numbers are

lassi simple ases, whereas both re ursive and iterative versions have been proposed for well-known algorithms su h as binary sear h, qui ksort and mergesort among others. In the sequel, rst we present a re ursive and then an iterative PASCAL variation for the al ulation of fa torials. These fun tions will be used for the al ulation of binomial

oeÆ ients. From the theoreti al point of view, both variants are equivalent sin e they perform O(n) operations to

al ulate n! However, from the pra ti al point of view, the previous omment holds: fun tion alls have a ost that is more signi ant in omparison to the ost spent for the

ontrol stru tures and other assignment operations. Also, have in mind that in this ase, the performed operations are multipli ations, but we use the general term operations instead of multipli ations, sin e the number of divisions will be equally important in the subsequent eorts. In other words, multipli ations and divisions are our barometer metri s in the ourse of estimating the algorithmi omplexity [4℄. FUNCTION Fa torial1(n: INTEGER): INTEGER; BEGIN IF n=0 THEN Fa torial:=1 ELSE Fa torial1:=n*Fa torial1(n-1) END; FUNCTION Fa torial2(n: INTEGER): INTEGER; VAR i,produ t: INTEGER; BEGIN i:=n; produ t:=1; WHILE i0 DO BEGIN produ t:=i*produ t; i:=i-1 END; Fa torial2:=produ t END;

The following ode fragment depi ts a PASCAL implementation of the rst re ursive solution for the binomial oeÆ ient al ulation, whi h has been reported in [6℄. Apparently, this implementation is very ineÆ ient sin e its omplexity is O(C(n,k)). More spe i ally, it performs 2C(n,k)1 multipli ations to al ulate C(n,k). FUNCTION Comb1(n,k: INTEGER): INTEGER; BEGIN IF (k=0) OR (k=n) THEN Comb1:=1 ELSE Comb1:=Comb1(n-1,k-1)+Comb1(n-1,k) END;

From the above starting point, we will move gradually to smarter solutions. First eort is to get rid of the re ursion. This an be a hieved by alling any of the previous two Fa torial fun tions. Although, the following straightforward fragment has a O(n) omputation omplexity, it has to be noted that there is a hidden onstant equal to 2. FUNCTION Comb2(n,k:INTEGER): INTEGER; VAR t1,t2,t3: INTEGER; BEGIN t1:=Fa torial2(n); t2:=Fa torial2(k); t3:=Fa torial2(n-k); Comb2:=t1/(t2*t3) END;

The previous iterative fun tion has made an impressive improvement in eÆ ien y in omparison to the Comb1 fun tion. However, further improvement an be a hieved by avoiding performing a ertain number of multipli ations on the numerator for a term that will be simpli ed by a same term of the denominator. The following fragment Comb3 is a PASCAL implementation in pla e of the se ond re ursive formula that has been reported in [6℄. Here, we remark that a division operation omes into play. The omputation

omplexity of Comb3 is O(k), i.e. irrelevant of n, with a hidden onstant equal to 2. This is derived by simply remarking that after simpli ations, both the numerator and denominator omprise of k terms. FUNCTION Comb3(n,k: INTEGER): INTEGER; BEGIN IF (k=0) THEN Comb3:=1 ELSE Comb3:=Comb3(n-1,k-1)*n/k END;

As mentioned in [6℄, the latter method an be improved by using the binomial oeÆ ient property that C(n,k)=C(n,nk). Next, we present a more eÆ ient iterative version based on this remark. Thus, the following Comb4 fragment rst

al ulates the maximum between k and n-k, in order to save a number of operations. Although Comb4 fragment is longer, apparently its omputation omplexity is O(min(k,nk)), also with a hidden onstant equal to 2.

FUNCTION Comb4(n,k:INTEGER): INTEGER; VAR t1,t2: INTEGER; BEGIN IF k...