[RESOLVED] Remove recursion

[ComputerJy]

Hi all
I need help converting this recursive function to non-recursive

int nnn(int n){
	if(n>1){
		return nnn(n-1)+nnn(n-2);
	}else{
		return 1;
	}
}

Function nnn(N as Integer) As Integer
    If N>1 Then 
        Return nnn(N-1)+nnn(N-2);
    Else
        Return 1;
    End If
End Function

[Starman]

Surprised to see this still open, here's my guess:
It looks like for any positive value of N, nnn(N) will return N.
For any value of N less than 1, nnn(N) will return 1.
Very simplified would be:
Function nnn(N as Integer) As Integer
If N>1 Then 'N is an integer value so >0 is 1 or more
Return N;
Else
Return 1;
End If
End Function

[Starman]

Whoops! didn't test far enough - that only works for values up to 3
looking......

[Starman]

There is a formula on here, and a working example (they say). It does look better as a recursive.

http://www.mcs.surrey.ac.uk/Personal...ibFormula.html


nnn(N) = (Phi^N – (–Phi)^–N)/sqrt(5)

where Phi = 1·61803 39887 49894 84820 45868 34365 63811 77203 09179 80576 ... .

[Starman]

not quite vb, but I expect you can understand this:
stolen from the page I referenced, and I've removed the warnings and overflow checks for clarity - it's close but lacks accuracy and best not call it with N=2.

function nnn(N number)return number
is
i number;
p1 number;
p2 number;
begin
i:=N;
p1:=power((sqrt(5)+1)/2,i)/sqrt(5);
p2=-power((-sqrt(5)+1)/2,i)/sqrt(5);
return trunc(p1+p2);
end;

[Starman]

I think the environment I was testing in was causing the inaccuracies I experienced, this seems fine in excel (paste into b1 and add N into a1):

=POWER((SQRT(5)+1)/2,A1)/SQRT(5)-POWER((-SQRT(5)+1)/2,A1)/SQRT(5)