1

This might sound like a School assignment but it is not!

I have made a recursive function returning a value from the Fibonacci Sequence. 

let rec FoneFive n =
    match n with
    | 1 | 2 -> 1
    | n -> FoneFive(n-1) + FoneFive(n-2)

printfn "%A" (FoneFive 6)

What is going on in this recursive function? FoneFive 6 gives 8 as it should. But why?

The way I see it: It starts with n=6 and concludes that 6 is not 1 or 2. So it calls FoneFive(n-1) + FoneFive(n-2). (This is probably where I get it wrong. But the way I see it is that this return nothing unless n is 1 or 2. So from my point of view it will narrow both down n = 1 or 2 and there by say 1 + 1 which of course is 2.)

Can someone tell me how it returns 8 ?

rajah9
  • 11,645
  • 5
  • 44
  • 57
Nulle
  • 1,301
  • 13
  • 28
  • 2
    Please see the Java recursive answer at http://stackoverflow.com/a/8965075/509840. F# works exactly the same way. – rajah9 Oct 13 '16 at 14:14
  • 3
    You're on the right track when you say it calls `FoneFive(n-1) + FoneFive(n-2)`. That means the call with `n=6` makes calls with `n=5` and `n=4`, which in turn make calls with smaller `n`, until you get to calls with 1 or 2 and can return an actual value. Track it through by hand, or with a debugger, to see how you get to 8. – pjs Oct 13 '16 at 14:40
  • 3
    Imagine `n` was 3. Then you'd return `FoneFive(n-1) + FoneFive(n-2)` = `FoneFive(2) + FoneFive(1)` = `1 + 1` = 2. So you can see that `FoneFive(3)` returns 2. That contradicts your last statement, so hopefully gives you the intuition to see why other values greater than `n=3` work too – Ben Aaronson Oct 13 '16 at 14:58

2 Answers2

6

Calculating FoneFive(6) requires to calculate FoneFive(5) and FoneFive(4)
(as 5 and 4 are n-1 and n-2 for n=6)

Calculating FoneFive(5) requires to calculate FoneFive(4) and FoneFive(3)
(as 4 and 3 are n-1 and n-2 for n=5)

Calculating FoneFive(4) requires to calculate FoneFive(3) and FoneFive(2)
(as 3 and 2 are n-1 and n-2 for n=4)

Calculating FoneFive(3) requires to calculate FoneFive(2) and FoneFive(1)
(as 2 and 1 are n-1 and n-2 for n=3)

Both FoneFive(1) and FoneFive(2) returns 1
so FoneFive(3) = FoneFive(2) + FoneFive(1) = 1 + 1 = 2
so FoneFive(4) = FoneFive(3) + FoneFive(2) = 2 + 1 = 3
so FoneFive(5) = FoneFive(4) + FoneFive(3) = 3 + 2 = 5
so FoneFive(6) = FoneFive(5) + FoneFive(4) = 5 + 3 = 8

Sehnsucht
  • 5,019
  • 17
  • 27
0

Okay so i get it now. It so to speak splits it selv up into two pieces every time n is not 1 or 2 and then again splits itself of to two pieces if that isn't 1 or 2 either. 

f6 = f5 + f4
f5 + f4 = f4 + f3 + f3 + (f2=1)
f4 + f3 + f3 + (f2=1) = f3 + (f2=1) + (f2=1) + (f1=1) + (f2=1) + (f1=1) + 1
f3 + 1 + 1 + 1 + 1 + 1 + 1 = (f2=1) + (f1=1) + 1 + 1 + 1 + 1 + 1 + 1
(f2=1) + (f1=1) + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8
Nulle
  • 1,301
  • 13
  • 28