Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**kylekatarn****Member**- Registered: 2005-07-24
- Posts: 445

Try to proof (or find a counter-example) the following statement:

*If a problem can be solved in a pure recursive way, does this implies that an iterative solution also exists?*

...This is something that came to my mind today during a lesson - Immediately called it *the R-I conjecture*

*Last edited by kylekatarn (2005-11-16 08:13:52)*

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,684

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

Offline

**kylekatarn****Member**- Registered: 2005-07-24
- Posts: 445

Another example where my 'conjecture' works

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

I don't think so.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

I'll find a counter-example

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Try to calculate

with iterative approach!

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

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**kylekatarn****Member**- Registered: 2005-07-24
- Posts: 445

What's wrong?

That is computable in a finite number of steps: )

acc := 0

i:=1

while i<n

{

acc:=acc+1/i^k

i:=i+1

}

in the end, return acc

//Edit: corrected the variable that was being incremented

*Last edited by kylekatarn (2005-12-31 14:13:12)*

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Oh,so "iterative" meant this?

Then...

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Then R-I conjecture must be true.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

kylekatarn wrote:

What's wrong?

That is computable in a finite number of steps: )acc := 0

k:=1while 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.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

Pages: **1**