How are my recursive calls not tail calls here?

Question

In the following code, all calls to retry get the warning "Recursive call is not a tail call":

private tailrec suspend fun <T> retry(numberOfRetries: Int, block: suspend () -> T): Result<T> =
    runCatching {
        Timber.d("retry($numberOfRetries)")
        block()
    }.fold(
        onSuccess = { Result.success(it) },
        onFailure = { throwable ->
            when (throwable) {
                is TimeoutCancellationException -> {
                    Timber.e(throwable, "Request ran into timeout - retrying immediately...")
                    if (numberOfRetries > 0) {
                        retry(numberOfRetries - 1, block)
                    } else {
                        Result.failure(throwable)
                    }
                }

                is HttpException -> {
                    if (throwable.code() == HttpStatusCode.NOT_FOUND_404) {
                        Timber.e(throwable, "Request returned 404 - don't retry!")
                        Result.failure(throwable)
                    } else {
                        Timber.e(throwable, "Request returned some other error code - retrying in 3 seconds...")
                        if (numberOfRetries > 0) {
                            delay(DELAY_BEFORE_RETRY_MS)
                            retry(numberOfRetries - 1, block)
                        } else {
                            Result.failure(throwable)
                        }
                    }
                }

                else -> {
                    Timber.e(throwable, "Some other problem with request - retrying in 3 seconds...")
                    if (numberOfRetries > 0) {
                        delay(DELAY_BEFORE_RETRY_MS)
                        retry(numberOfRetries - 1, block)
                    } else {
                        Result.failure(throwable)
                    }
                }
            }
        }
    )

1. Why?
2. Is there a way to rewrite this function to make it tail recursive?

Answer 1

1. Why?

Looks like the tailrec detection doesn't go through inline higher-order functions. You're using fold here and passing callbacks, you're not calling retry directly from retry's body.

Here is a simpler example demonstrating the issue:

private tailrec fun doThing(count: Int) {
    inlineLambdaWrap {
        if (count > 0) {
            doThing(count - 1) // Warning: Recursive call is not a tail call
        } else {
            println("STOP")
        }
    }
}

private inline fun inlineLambdaWrap(block: () -> Unit) {
    block()
}

2. Is there a way to rewrite this function to make it tail recursive?

I think tail recursion is also not supported in try/catch/finally blocks, so getting rid of the runCatching/fold will not help in this sense.

If you really really want recursion here, you can probably get around it using Ivo's answer.

That being said, retrying is rather inherently a repetition, so I wouldn't go with a recursive approach in the first place. Using recursion makes it unclear which error will end up being reported for instance. It also adds a bunch of extra ifs in your current code. How about this?

private suspend fun <T> retryRequest(numberOfRetries: Int, block: suspend () -> T): Result<T> {
    lateinit var lastError: Throwable
    repeat(numberOfRetries) { attempt ->
        try {
            Timber.d("retry(${numberOfRetries - attempt})")
            return Result.success(block())
        } catch (e: TimeoutCancellationException) {
            Timber.e(e, "Request ran into timeout - retrying immediately...")
            lastError = e
        } catch (e: HttpException) {
            if (e.code() == HttpStatusCode.NOT_FOUND_404) {
                Timber.e(e, "Request returned 404 - don't retry!")
                return Result.failure(e)
            } else {
                Timber.e(e, "Request returned some other error code - retrying in 3 seconds...")
                delay(DELAY_BEFORE_RETRY_MS)
                lastError = e
            }
        } catch (t: Throwable) {
            Timber.e(t, "Some other problem with request - retrying in 3 seconds...")
            delay(DELAY_BEFORE_RETRY_MS)
            lastError = t
        }
    }
    return Result.failure(lastError)
}

I would even go as far as saying don't use Result in business code, and just throw, but that impacts your signature so I won't change it.

Also, note that you're catching Throwable which means you're catching WAY MORE than just request errors here - which makes your message misleading.

Answer 2

I believe there are two reasons why tail recursion doesn't work here. The first thing is that it doesn't work within lambdas. For example, even this gives a warning

private tailrec suspend fun <T> retry(numberOfRetries: Int, block: suspend () -> T): Result<T> =
    run {
        retry(numberOfRetries - 1, block)
    }

Also, it doesn't work inside a try/catch, which essentially happens within a runCatching. For example, this also gives a warning

private tailrec suspend fun <T> retry(numberOfRetries: Int, block: suspend () -> T): Result<T> =
    try {
        Result.success(block())
    } catch (e: Throwable) {
        retry(numberOfRetries - 1, block)
    }

I think you can rewrite it to simply return the recursion at the end like this

private tailrec suspend fun <T> retry(numberOfRetries: Int, block: suspend () -> T): Result<T> {
    try {
        Timber.d("retry($numberOfRetries)")
        return Result.success(block())
    } catch (throwable: Throwable) {
        when (throwable) {
            is TimeoutCancellationException -> {
                Timber.e(throwable, "Request ran into timeout - retrying immediately...")
                if (numberOfRetries <= 0) {
                    return Result.failure(throwable)
                }
            }

            is HttpException -> {
                if (throwable.code() == HttpStatusCode.NOT_FOUND_404) {
                    Timber.e(throwable, "Request returned 404 - don't retry!")
                    return Result.failure(throwable)
                } else {
                    Timber.e(throwable, "Request returned some other error code - retrying in 3 seconds...")
                    if (numberOfRetries > 0) {
                        delay(DELAY_BEFORE_RETRY_MS)
                    } else {
                        return Result.failure(throwable)
                    }
                }
            }

            else -> {
                Timber.e(throwable, "Some other problem with request - retrying in 3 seconds...")
                if (numberOfRetries > 0) {
                    delay(DELAY_BEFORE_RETRY_MS)
                } else {
                    return Result.failure(throwable)
                }
            }
        }
    }
    return retry(numberOfRetries - 1, block)
}

But I'm not entirely sure if this works

Answer 3

Thanks to the answers by @Joffrey and @Ivo I was able to figure out a solution. As you both suggested, the callback lambdas inside of fold don't "count".

The following code does exactly what my original one did but now it is actually recognized as tail recursive:

private tailrec suspend fun <T> retry(numberOfRetries: Int, block: suspend () -> T): Result<T> {
    val result = runCatching {
        Timber.d("retry($numberOfRetries)")
        block()
    }

    return if (result.isSuccess) {
        result
    } else {
        when (val throwable = result.exceptionOrNull()!!) {
            is TimeoutCancellationException -> {
                Timber.e(throwable, "Request ran into timeout - retrying immediately...")
                if (numberOfRetries > 0) {
                    retry(numberOfRetries - 1, block)
                } else {
                    result
                }
            }

            is HttpException -> {
                if (throwable.code() == HttpStatusCode.NOT_FOUND_404) {
                    Timber.e(throwable, "Request returned 404 - don't retry!")
                    result
                } else {
                    Timber.e(throwable, "Request returned some other error code - retrying in 3 seconds...")
                    if (numberOfRetries > 0) {
                        delay(DELAY_BEFORE_RETRY_MS)
                        retry(numberOfRetries - 1, block)
                    } else {
                        result
                    }
                }
            }

            else -> {
                Timber.e(throwable, "Some other problem with request - retrying in 3 seconds...")
                if (numberOfRetries > 0) {
                    delay(DELAY_BEFORE_RETRY_MS)
                    retry(numberOfRetries - 1, block)
                } else {
                    result
                }
            }
        }
    }
}

However, originally retry returned only a T, not a Result<T>, and contained a simple try with multiple catches - again, as you both suggested! (But, of course, that wasn't tail recursive either)

Changing it to Result<T> was just part of my experiments to make it tail recursive. So, I think I will use the following as my solution:

private tailrec suspend fun <T> retry(numberOfRetries: Int, block: suspend () -> T): T {
    val result = runCatching {
        Timber.d("retry($numberOfRetries)")
        block()
    }

    if (result.isSuccess) {
        return result.getOrNull()!!
    } else {
        when (val throwable = result.exceptionOrNull()!!) {
            is TimeoutCancellationException -> {
                Timber.e(throwable, "Request ran into timeout - retrying immediately...")
                if (numberOfRetries > 0) {
                    return retry(numberOfRetries - 1, block)
                } else {
                    throw throwable
                }
            }

            is HttpException -> {
                if (throwable.code() == HttpStatusCode.NOT_FOUND_404) {
                    Timber.e(throwable, "Request returned 404 - don't retry!")
                    throw throwable
                } else {
                    Timber.e(throwable, "Request returned some other error code - retrying in 3 seconds...")
                    if (numberOfRetries > 0) {
                        delay(DELAY_BEFORE_RETRY_MS)
                        return retry(numberOfRetries - 1, block)
                    } else {
                        throw throwable
                    }
                }
            }

            else -> {
                Timber.e(throwable, "Some other problem with request - retrying in 3 seconds...")
                if (numberOfRetries > 0) {
                    delay(DELAY_BEFORE_RETRY_MS)
                    return retry(numberOfRetries - 1, block)
                } else {
                    throw throwable
                }
            }
        }
    }
}

At least for now...