A question from someone who’s not familiar with fu...

# functional

[JP]

A question from someone who’s not familiar with functional programming: I read that any recursive functions could be converted into tail-recursive function using something called continuation passing style from functional programming paradigm. I tried to practice with it with my own example function of reversing a singly linked list, but I’m kind of stuck. I think just by looking at a trivial examples like factorial or fibonacci function wasn’t enough for me to understand the concept. Could anyone give me a help, or point to a good reference (rather easy to understand for beginners) regarding this matter?

Untitled

[raulraja]

There are two options here to keep recursion safe. Attempt to rewrite the function so you handle terinal case emptyList + recurse over head + remaining el in tail position or introducing trampolines. Trampolines jump the stack every so often frames to avoid StackOverFlow moving the remaining of the computation to the heap and back to the stack. AndThen in Arrow helps trampolining

[JP]

Could you please elaborate more? I wasn’t really able to comprehend from sentence “Attempt to rewrite the function so you handle terinal case emptyList + recurse over head + remaining el in tail position or introducing trampolines.” I would first like to understand how to convert the function to tail-recursive function, without using higher level abstractions or additional functional programming library. I was trying to find a source which explains continuous passing style in simplified manner, but I wasn’t able to.

[julian]

@JP Yes, I think it's a good idea to master converting recursion to tail-recursion first. You don't need continuation passing or functional programming for that. And those two are much wider and deeper topics, especially FP. I highly recommend Chapter 4 of Joy of Kotlin by @pysaumont for tail-recursion in particular, and non-library-specific FP in general. Otherwise, you can probably find articles on the internet on the topic.

Beyond that, Kotlin coroutines are an implementation of continuation passing style. You may find understanding CPS easier by searching for and reading articles on how Kotlin converts suspend functions to coroutines.

[JP]

@julian Thanks for the comment. But is it possible to convert the above function to tail recursion without using continuation passing? In general, can all recursive functions be converted to tail recursive ones even without the notion of continuation passing?

[julian]

@JP Yes, your function can be converted to tail recursion. To see if you're successful in doing so, apply the Kotlin tailrec keyword to the function and see whether the compiler recognizes your implementation as being tail-recursive. I don't know if all recursion can be converted to tail-recursion, but all the cases I've encountered have been convertible. Though it always involves some refactoring of the function itself, sometimes extensively. Yes, tail-recursion can be achieved without continuation passing. But there may be a subset of cases where continuation passing is required or preferred.

[julian]

These are not trivial topics to learn and master. But if you set your mind to it, and apply patient effort, all is possible.

[JP]

Thank you, I did manage to rewrite the function in tail-recursion without CPS, but I’d still like to learn the concept of it. I found this page https://www.it.uu.se/edu/course/homepage/avfunpro/ht10/notes/html/f06-cps.html and with the factorial example I managed to understand that defining the continuation as such, and applying the initial continuation as identity function makes it work, but I still wasn’t able to grasp the generalized concepts, so that I could apply for functions other than the simple examples like factorial or fibonacci. I’d be grateful if someone could point to a nice reference regarding the topic which possibly contains some generous explanations for beginners.