VB Recursion and Fibonacci sequence

Question

OK. I know this is a classic but I cant seem to find any threads explaining how the trace table would work. My own attempts look like faulty logic. For example this code works great:

 Sub Main()
        For i = 1 To 6
            Console.WriteLine(f(i))
        Next
        Console.ReadKey()
 End Sub

Then we have the Function:

Function f(n)
        If n <= 1 Then
            Return n
        Else
            n = f(n - 1) + f(n - 2)
            Return n
        End If
    End Function

However, my trace table ends up like this:

i  f-1  f-2  n
1            1
2   1    0   1
3   2    1   3
4   3    2   5
5   4    3   7
6   5    4   9

Which makes perfect sense to me, but obviously shows I dont have a clue. What is the faulty logic here??

Answer 1

Your trace table makes no sense since the f-1 column should be named f(n-1) and currently only shows i-1.

If I fix a few of the mistakes you have made, I obtain the following piece of code (highlighted in boldface):

Public Module modmain

Function f(n) As Integer
    If n <= 1 Then
        Return n
    Else
        n = f(n - 1) + f(n - 2)
        Return n
    End If
End Function

 Sub Main()
        For i as Integer = 1 To 6
            Console.WriteLine(f(i))
        Next
        Console.ReadKey()
 End Sub

End Module

I obtain the correct output for the first six Fibonacci elements:

$  vbnc fib.vb 
Visual Basic.Net Compiler version 0.0.0.5943 (Mono 4.0.1 - tarball)
Copyright (C) 2004-2010 Rolf Bjarne Kvinge. All rights reserved.

A warning message should have been shown: 'Parameter type should be specified.'
Assembly 'fib, Version=0.0, Culture=neutral, PublicKeyToken=null' saved successfully to '/home/kommusoft/testfolder/fib.exe'.
Compilation successful
Compilation took 00:00:00.7312840
$ mono fib.exe 
1
1
2
3
5
8

For the trace table, you have to rename your columns such that they look like:

i  f(i-1)  f(i-2)  f(i)

Now for the first two is (i=0 and i=1) you can simply fill in 0 and 1 in the last column:

i  f(i-1)  f(i-2)  f(i)
0                     0
1                     1

Now for the next row, f(i-1) and f(i-2) can be looked up in the part of the table you already filled in:

i  f(i-1)  f(i-2)  f(i)
0                     0
1                     1
2       1       0     1

i  f(i-1)  f(i-2)  f(i)
0                     0
1                     1
2       0       1     1
3       1       1     2

etc.