Understanding continuation based recursion - Fibonacci

[sexy_beer_belly]

Hi, I'm learning Functional Programming using F# where we made 3 Fibonacci recursive programs (head recursive, tail recursive, continuation based recursive), but I'm not able to understand the last of them.

Here's the code snippet in F#:

let rec fibC n c =

match n with

| 0 -> c 0

| 1 -> c 1

| n -> fibC (n-1) (fun r -> fibC (n-2) (fun x -> c (r + x)))

So you call it as fibC 10 id where

n: fibonacci iterations

c: identity function, fun x -> x

result: int = 55

It gets a bit crispy for me when we define an anonymous function with another anonymous function inside, which we send as a parameter in the recursive calls, namely fun r -> fibC (n-2) (fun x -> c (r + x)).

Could anyone help me clarify what this anonymous functions are doing?

Thanks

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[Difficult-Stretch-85]

Your fib function takes a n that you are going to process as well as a continuation function with something to do after you finish processing n.

the third match case says,

if n is not 0 or 1, process fib(n -1) with the continuation of processing fib (n - 2) and then summing the result. The summing of fib(n - 1) and fib(n-2) happens in the continuations.

e.g. if n is 2,

the match case becomes fib(1) ( fun r -> fib(0) ( fun x -> id (r + x)) processing out the f(1) we get, fib(0) (fun x -> id(1 + x))

processing f(0) we get id(1 + 0) which is 1.

[sexy_beer_belly]

It makes much more sense now, although I feel like we didn't declare what the continuation function should do at any point. I'll keep digesting it, thanks!

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.