Math Is Fun Forum

kylekatarn

Member

Registered: 2005-07-24

Posts: 445

.

.

Last edited by kylekatarn (2020-01-04 02:05:29)

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,713

Re: .

In programming the assumption is "yes", but I don't know for sure.

For the purpose of discussion, here are example of each method (NOT written for computer efficiency!)

Task: You want to reverse the order of letters, so that "fred" becomes "derf"

Iterative Approach

reverse(s) {
    for (i=length(s), i>0, i--) {          // go backwards through s
        snew = snew & mid(s,i,1);  // extract the letter at that spot
    }
    return( snew );
}

Recursive Approach

reverse(s) {
    if (length(s) > 1) {
        // split s into last character and the rest
        slast = right(s,1);   
        sleft = left(s,length(s)-1) 
        return ( slast & reverse(sleft) );       // then call this function again with shorter s
    } else {
        return( s );
    }
}

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

I don't think so.

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

I'll find a counter-example

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

Try to calculate

with iterative approach!

Last edited by krassi_holmz (2005-12-31 01:38:22)

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

Oh,so "iterative" meant this?
Then...

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

Then R-I conjecture must be true.

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

First we must define what are the differences between the Iterative and Recursive approach.

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

What's wrong?
That is computable in a finite number of steps: )

acc := 0
k:=1

while i<n
{
   acc:=acc+1/i^k
   k:=k+1
}
in the end, return acc

You have forgotten one line:
while i<n
{
acc:=acc+1/i^k
k:=k+1
i:=i+1
}

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

Recursive:
Let use this:
a[i]=F[a[1],a[2],...,a[i-1]] depends of a[1..(i-1)]
We must fund iteractive approach.

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: .

a[1]=const
a[2]=F[a[1]]
a[3]=F[a[1],a[2]]
a[4]=F[a[1],a[2],a[3]]

---

IPBLE:  Increasing Performance By Lowering Expectations.