COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Rewrite recursive function as non-recursive.

• Email
• Follow

```NB -- A copy of this message is also posted in ng:
borland.public.delphi.students

Hi All,

The following function is part of a program which generates a
Pascal's Triangle. It uses recursion (as you can see), however, I need
a non-recursive version of it. I believe that the technique I'm
referring  to is called "tail recursion".

Can anyone please assist me and rewrite this function so that it  does
not use recursion (call itself) ??? -- e.g. obviously it would need to
use tail recursion, and that's what I'm after.

function GetPascalPyramidValue(const X, Y: Integer): Integer;
begin
if (X = 0) and (Y = 0) then
Result := 1
else if (Y = 0) then
Result := 0
else
Result := GetPascalPyramidValue(X, Y - 1)
+ GetPascalPyramidValue(X - 1, Y - 1);
end; // of function GetPascalPyramidValue

Regards,
Peter W. :-)))
Sandy Bay, Hobart, Tas, AU.
```
 0
Reply pew (7) 4/25/2005 11:53:30 PM

See related articles to this posting

```On Mon, 25 Apr 2005 23:53:30 GMT, "Peter Williams"
<pew@bigpond.net.au> wrote:

>	The following function is part of a program which generates a
>Pascal's Triangle. It uses recursion (as you can see), however, I need
>a non-recursive version of it. I believe that the technique I'm
>referring  to is called "tail recursion".

I think you can eliminate the recursion in this, since it is tail
recursion, but it would be much better to write it to fill in a row at
the time, left to right.

---
Replace you know what by j to email
```
 0

```JRS:  In article <_pfbe.24804\$5F3.14944@news-server.bigpond.net.au>,
dated Mon, 25 Apr 2005 23:53:30, seen in news:comp.lang.pascal.misc,
Peter Williams <pew@bigpond.net.au> posted :
>NB -- A copy of this message is also posted in ng:
>borland.public.delphi.students

>       The following function is part of a program which generates a
>Pascal's Triangle. It uses recursion (as you can see), however, I need
>a non-recursive version of it. I believe that the technique I'm
>referring  to is called "tail recursion".
>
>       Can anyone please assist me and rewrite this function so that it  does
>not use recursion (call itself) ??? -- e.g. obviously it would need to
>use tail recursion, and that's what I'm after.
>
>function GetPascalPyramidValue(const X, Y: Integer): Integer;
>begin
>  if (X = 0) and (Y = 0) then
>    Result := 1
>  else if (Y = 0) then
>    Result := 0
>  else
>    Result := GetPascalPyramidValue(X, Y - 1)
>      + GetPascalPyramidValue(X - 1, Y - 1);
>end; // of function GetPascalPyramidValue

Well, IIRC, the answer is just (X+Y)!/(X!*Y!) or something similar, so
you could just use that, if you can avoid intermediate overflow.

Since all results are non-negative, you could declare a global array
A[0..Xmax,0..Ymax] and fill it with -1.  Then the function looks up the
answer in the array; if it gets -1 it calculates it as above, returning
the answer after storing it in the array.  Clearly, no value will ever
be recalculated, and no unnecessary value will be calculated.

If it's coursework, neither of those solutions will do.

<URL:http://www.merlyn.demon.co.uk/programs\pastri.pas>.

--
� John Stockton, Surrey, UK.  ?@merlyn.demon.co.uk   Delphi 3   Turnpike 4 �
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.bancoems.com/CompLangPascalDelphiMisc-MiniFAQ.htm> clpdmFAQ;
<URL:http://www.borland.com/newsgroups/guide.html> news:borland.* Guidelines
```
 0

```Hi John,

Dr John Stockton wrote:

>
> Well, IIRC, the answer is just (X+Y)!/(X!*Y!) or something similar, so
> you could just use that, if you can avoid intermediate overflow.

Actually, it's:

Y! div (X!*(Y-X)!)

where: X is the number being calculated, starting at 1,
Y is the level, starting at 0.

>
> Since all results are non-negative, you could declare a global array
> A[0..Xmax,0..Ymax] and fill it with -1.  Then the function looks up
> the answer in the array; if it gets -1 it calculates it as above,
> returning the answer after storing it in the array.  Clearly, no
> value will ever be recalculated, and no unnecessary value will be
> calculated.
>
> If it's coursework, neither of those solutions will do.
>
> <url: http://www.merlyn.demon.co.uk/programs\pastri.pas>.
>

I was emailing someone who is a lecturer and sets this as a problem
for this class. He also mentioned that there is a solution using
array(s). There are actually many ways to solve this problem. :-)))

Regards,
Peter W. :-)))
Sandy Bay, Hobart, Tas, AU.
```
 0

```On Wed, 27 Apr 2005 23:18:00 GMT, "Peter Williams"
<pew@bigpond.net.au> wrote:

>	I was emailing someone who is a lecturer and sets this as a problem
>for this class. He also mentioned that there is a solution using
>array(s). There are actually many ways to solve this problem. :-)))

Yes, you can calculate the terms directly from the formula, you can
use arrays, or you can use recursion.  The array method uses the most
memory (but that probably isn't important in this case).  Recursion
uses little memory, but it takes a lot of computation for this problem
because it recalculates most of the values many times.

---
Replace you know what by j to email
```
 0

```JRS:  In article <f0b0715hb67uht3t7vn89epko81ooh0i07@4ax.com>, dated
Wed, 27 Apr 2005 20:21:23, seen in news:comp.lang.pascal.misc, Jud
>On Wed, 27 Apr 2005 23:18:00 GMT, "Peter Williams"
><pew@bigpond.net.au> wrote:
>
>>      I was emailing someone who is a lecturer and sets this as a problem
>>for this class. He also mentioned that there is a solution using
>>array(s). There are actually many ways to solve this problem. :-)))
>
>Yes, you can calculate the terms directly from the formula, you can
>use arrays, or you can use recursion.  The array method uses the most
>memory (but that probably isn't important in this case).  Recursion
>uses little memory, but it takes a lot of computation for this problem
>because it recalculates most of the values many times.

ISTM that one could also use a linked-list structure; each item would
require more memory (but in the Heap), but items would only be created
when calculated.  Lookup would be a lot slower than with a 2D-array, but
much quicker than basic recursion.  A double-linked structure might
help.

--
� John Stockton, Surrey, UK.  ?@merlyn.demon.co.uk   Turnpike v4.00   MIME. �
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.merlyn.demon.co.uk/clpb-faq.txt>   RAH Prins : c.l.p.b mFAQ;
<URL:ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ.
```
 0

```On Thu, 28 Apr 2005 23:06:29 +0100, Dr John Stockton
<spam@merlyn.demon.co.uk> wrote:

>ISTM that one could also use a linked-list structure; each item would
>require more memory (but in the Heap), but items would only be created
>when calculated.  Lookup would be a lot slower than with a 2D-array, but
>much quicker than basic recursion.  A double-linked structure might
>help.

Yes, you could use a linked list.  However, the numbers in Pascal's
triangle get large pretty quickly, so in practice I don't think that
memory or running time will be the limiting factor (unless you go to
unlimited precision).  For 32 bit integers, it isn't going to take
much memory before you get to as large of integers you can deal with.
(You only need to store two lines, not the whole array, if you output
them along the way.)  Running time on the recursive version might be a
problem, though, even with 32-bit integers.

---
Replace you know what by j to email
```
 0

```Peter Williams wrote:

>        Actually, it's:
>
>        Y! div (X!*(Y-X)!)
>
>        where: X is the number being calculated, starting at 1,
>                 Y is the level, starting at 0.

Faculties are inconvenient because they result in overflows at even very
moderate operands. You can however calculate such faculties using the
logarithm of the gamma-function. The gamma-function is the equivalent to
faculties for real numbers.

function LnGamma (x : double) : double;

const a0 =  0.083333333096;
a1 = -0.002777655457;
a2 =  0.000777830670;
c  =  0.918938533205;

var  r : double;

begin
r:= (a0 + (a1 + a2 / sqr(x)) / sqr(x)) / x;
LnGamma:= (x - 0.5) * ln(x) - x + c + r;
end;

function LnFak (x : longint) : double;

begin
LnFak := LnGamma(succ(x));
end;

You can then calculate the ln of the pyramid values:

LnPyramid := LnFak(y) - (LnFak(x) + LnFak(y-x));
Pyramid := exp(LnPyramid)

There are also a number of special cases, which should be dealt with
separately:

function BinominalKoeffizient (n, k :longint) : LongInt;

var x : double;

begin
if n < k
then
BinominalKoeffizient := 0
else
if (n=k) or (k=0)
then
BinominalKoeffizient := 1
else
if k=1
then
BinominalKoeffizient := n
else
begin
x := LnFak(n) - (LnFak(k) + ln(n-k));
BinominalKoeffizient := round(exp(zwischen));
end;
end;

I have used that function for statistical calculations and never
encountered an overflow, although one can certainly generate one with
unrealistic values for n and k.

```
 0

7 Replies
482 Views

Similar Articles

12/10/2013 9:40:12 PM
page loaded in 132094 ms. (0)

Similar Artilces:

Sed: merging lines recursively depending on line pattern #2
This was probably answered elsewhere, but I haven't been able to find anything relevant. I have a file with sequence alignments. The format is the following: >name1 [variable number of lines containg the sequence, [A-Z] and - characters] >name2 [variable number of lines containg the sequence, [A-Z] and - characters] .... I want to merge the sequence lines on one line (and remove the spaces, but that's trivial). I then remove certain names and sequences but that's easy. I'm having trouble handling the variable number of sequence lines. Here's what I have and what I ...

Mapping Function
Hi all, I have the following being defined in a A.cxx file. // define in source file. Not exported to the outside world (this cannot be // moved to the header file [restriction]) #define CHANNEL_0 0 #define CHANNEL_1 1 #define CHANNEL_2 2 #define CHANNEL_3 3 #define CHANNEL_4 4 #define CHANNEL_5 5 However, in another file B.cxx, I have a fucntion called: registerChannel(int channelNumber_) { // perform registration via channel number (valid range 0 - 5) register(channelNumber_); } It works fine. However, now there is a new requirements: Channel 0,2,4 must maps to 0, 1, 2. Other ...

Events Function
I am getting the following error message when using ode15 with an event function: ??? SWITCH expression must be a scalar or string constant. Error in ==> funfun\private\odeevents at 32 switch lower(eventFcn) Error in ==> ode15s at 263 [haveEventFcn,eventFcn,eventArgs,valt,teout,yeout,ieout] = ... Error in ==> Systems_6DOF_init at 185 [t,x,te,xe,ie] = ode15s('SystemSimulation', tspan, x0, options); I've basically copied and pasted the "events" function from the ballode example to fit my code. The m file to detect events, is literally 3 lines long just li...

Arguments and Functions
Dear Group, I am attempting to modify a portion of the source code for the global illumination raytracer, RADIANCE. Specifically, I am trying to implement a different ray/triangle intersection algorithm. My C programming skills are laymen at best but I have successfully implemented this algorithm for triangle polygons (the source code that I am trying to modify is for a triangular mesh) previously. I have a question concerning passing arguments on to functions. For all that I have read and experienced, if there is a function that requires two arguments, then those arguments must be with the ...

function call
Hi, I am a little confused by the following example: portCHAR myaddress = 0xFF; ReadRegister(myaddress); void ReadRegister(portSHORT address); The compiler isn't giving me a warning for using a portCHAR(8 bit) as a parameter when portSHORT(16 bit) is used. But even though I expected the compiler to do "something" and assign 0x00FF to address, this was not the case. Inside the function ReadRegister "address" is 0x??FF with ?? being something undeterministic. It is not "auto-casting" to 0x00FF. I am fine with this functionality ... but I don't get it why ...

The function alpha
I have a gray scale image displayed using imshow(). I also have a number of fill objects displayed on the image. I am trying to change the transparency of these objects using the function alpha, but it doesn't seem to be working. It works fine when I use it in a simple figure. Am I missing something. Can anyone help me out here? Thanks, Vishal Mahulkar ...

pointer to a member function?
Hi everybody, I was wondering if there is an easy solution to this problem in order to avoid writing some extra code: I have a template class that has a member function called map: template <class P> class Q { typedef P::R RType; ... RType* map(P*, P*, int) { ... // do some stuff } }; Now, in another function contained in class Q, I need to sort a vector and for that I use a functor: template <class P> class SortFunctor { typedef typename P::R RType; P* p1_; P* p2_; public: SortFunctor(P* p1, P* p2) : p1_(p1), p2_(p2) {} bool opera...

pointer to a member function
How does one setup a pointer to a member function? In C, I usually do: void (*SetKey)(char); // declare a pointer to a function SetKey = &gPrefs->SetUp; // set the pointer to a valid function SetKey(lMsg.wParam); // call the function pointed to but I get errors in cpp, how do I do this? Thanks Allan "Allan Bruce" <allanmb@TAKEAWAYf2s.com> wrote in message news:bqgd5r\$ql8\$1@news.freedom2surf.net... > How does one setup a pointer to a member function? > In C, I usually do: > > void (*SetKey)(char); // declare a pointer to a function > SetKey = &gP...

cumulative density function
Dear PEOPLE, I have a question regarding data interpretation using Matlab. I have some data generate from a random process that interests me. The command hist(x,2^5) gives me a histogram , which is more of a quantized pdf or more correctly a probability mass function. I would like to obtain a pure pdf and even more important a pure cumulative density function i.e. the data should be able to tell the reader that if I have two random sources, how much of the two sources is less than 1, less than 2. The cdf gives this idea. So can you please tell me as to what commands could I use to interpret m...

Add and object or a function?
I am playing with a script that will allow columns of a table to be moved by dragging them left or right. To do this with functions is fairly straight forward, however after looking at Richard Cornford's version of Table Highlighter[1] I decided to do it using an object. Richard's basic code structure is: var SomeObject = (function() { function someFn01(){ // statements // return something } function setOnEvent01(arg1, arg2){ return (function() { // statements }); } return (function(arg1, arg2, argN){ // use...

Visibility of Protected Functions
Given this code: class A { private: void Priv() {}; protected: void Pro() {}; }; class B : public A { public: void Understanding( A *otherA, B *otherB ) { Priv(); otherA->Priv(); otherB->Priv(); Pro(); otherA->Pro(); otherB->Pro(); } }; Then in B::Understanding(), I understand that in the first three calls to Priv(), the function A::Priv() is inaccessible and will be flagged as errors by the compiler. In the calls to Pro(), I understand that the call to this->Pro() is absolutely fine. I also understand that in otherA->Pro(), ...

java trigonometry functions
hi, does java have the trig functions 'sec, cosec, cot' and also their inverses 'arcsec, arcosec & arcot' ? i am paricularly interested in 'arc cot' thanks jeremy watts On Feb 11, 1:35 pm, "Jeremy Watts" <jwatts1...@hotmail.com> wrote: > hi, > > does java have the trig functions 'sec, cosec, cot' and also their inverses > 'arcsec, arcosec & arcot' ? > > i am paricularly interested in 'arc cot' > > thanks > jeremy watts sec z = 1/cos z csc z = 1/sin z cot z = 1/tan z asec z = acos 1/z ac...

Function Graphics Bugs Depressing
Folks, The latest batch of function graphics bugs I am working on is turning me into a depressed shell of a programmer. Most of the bugs in my recent Bug a Day presentation schedule seem benign enough to me. At least I can imagine that someone could go into the code and fix them in a relatively short amount of time. The bugs I am working on today, however, seem to be of a different sort. They seem to be ingrained into the fabric of the function graphics design. I might call them "bugs of unintended consequence." It is exactly what one might expect of an overly complex system th...

higher-order-function library?
Is there an open source lisp project with the fp utilities like curry conjoin and disjoin? Thanks in advance, Andrew "andrew.baine@gmail.com" <andrew.baine@gmail.com> writes: > Is there an open source lisp project with the fp utilities like curry > conjoin and disjoin? Alexandria has those. <http://common-lisp.net/project/alexandria/> -- Luís Oliveira http://student.dei.uc.pt/~lmoliv/ On 8 Sie, 00:01, "andrew.ba...@gmail.com" <andrew.ba...@gmail.com> wrote: > Is there an open source lisp project with the fp utilities like curry >...

Non-Jet OLEDB backends?
I am developing in c++, OLEDB, and targeting the Jet backend. I have realized late in the project that the Jet backend is too slow, and I need to retarget. I do not want to rewrite my source code. I do not want to pay royalties. I want better performance. The application is single user, local access only, but needs high performance. Fancy features are not required in general ... Can anyone recommend a new backend? RDeW "Riley DeWiley" <riley.dewiley@gmail.com> wrote in message news:10oc31kjlfii0ec@corp.supernews.com... > I am developing in c++, OLEDB, and targeting the ...

BITAND, BITOR, BITXOR functions?
Has anyone ever used the BITAND, BITOR or BITXOR functions? I'm curious as to what they do, but the doc examples are pretty sparse and I can't extrapolate any possible usages out of them. Does anyone have any ideas as to what sort of purpose they could be used for? Why would someone need them? I'm not really looking for code, but if anyone has any samples, that could be helpful in figuring out what I could use them for myself, as they are one of the few REXX functions that I can't think of any way to apply to a practical problem. Thanks! John wrote: > Has anyon...

interactive function restricted to region
Hi, I have some functions which perform a search and replace, but I would like to restrict them to search only the region between the mark and the cursor, pretty much the same as "M-x replace-string" does. I appreciate any pointers in the right direction. -- Alex domain: iki dot fi localpart: alext email: localpart at domain Alex schrieb: > Hi, > > I have some functions which perform a search and replace, but I would > like to restrict them to search only the region between the mark and the > cursor, pretty much the same as "M-x replace-string" does....

Debug (sympy-Function; lambdify)
This is the code I m trying to run: from sympy import * import numpy as np from sympy import symbols def deriv(x,t): a = array(x) for i in range(0,len(x)): temp = x[i] a[i] = temp[0].diff(t) return a def matrixmult (A, B): C = [[0 for row in range(len(A))] for col in range(len(B[0]))] for i in range(len(A)): for j in range(len(B[0])): for k in range(len(B)): C[i][j] += A[i][k]*B[k][j] return C l1,l2,m1,m2,t = symbols('l1,l2,m1,m2,t') g = 10 th1 = Function('th1')(t) th2 = Fu...