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

You are not logged in.

## #1 2005-11-16 08:07:07

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

### Theory of Computation - Prove this!

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

## #2 2005-11-16 09:23:53

MathsIsFun
Registered: 2005-01-21
Posts: 7,657

### Re: Theory of Computation - Prove this!

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

## #3 2005-11-16 13:04:31

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

### Re: Theory of Computation - Prove this!

Another example where my 'conjecture' works

Offline

## #4 2005-12-31 01:31:47

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

### Re: Theory of Computation - Prove this!

I don't think so.

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

## #5 2005-12-31 01:33:04

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

### Re: Theory of Computation - Prove this!

I'll find a counter-example

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

## #6 2005-12-31 01:35:40

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

### Re: Theory of Computation - Prove this!

Try to calculate

with iterative approach!

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

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

## #7 2005-12-31 02:05:35

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

### Re: Theory of Computation - Prove this!

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

## #8 2005-12-31 13:19:26

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

### Re: Theory of Computation - Prove this!

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

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

## #9 2005-12-31 13:20:59

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

### Re: Theory of Computation - Prove this!

Then R-I conjecture must be true.

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

## #10 2005-12-31 13:28:14

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

### Re: Theory of Computation - Prove this!

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

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

## #11 2005-12-31 13:30:56

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

### Re: Theory of Computation - Prove this!

kylekatarn wrote:

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.

Offline

## #12 2005-12-31 13:34:23

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

### Re: Theory of Computation - Prove this!

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

## #13 2005-12-31 13:41:30

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

### Re: Theory of Computation - Prove this!

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