Recursion and Tail Recursion

A function that calls itself is known as recursive function. This technique is known as recursion. A physical world example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.

How does recursion work in programming?

Here, the recurse() function is called from the body of recurse() function itself. Here’s how this program works.


Example

Here, the recursive call continues forever causing infinite recursion. To avoid infinite recursion, if…else (or similar approach) can be used where one branch makes the recursive call and other doesn’t.

Find factorial of a Number using Recursion


Example
How this program works?

 

If you run the program, then this could be the step by step output:

      1. factorial(4)
      2. 4*factorial(3)
      3. 4*(3*factorial(2))
      4. 4*(3*(2*factorial(1)))
      5. 4*(3*(2*1))
      6. 24

Kotlin Tail Recursion

Tail recursion is a generic concept rather than the feature of Kotlin language. Some programming languages including Kotlin use it to optimize recursive calls.

What is tail recursion?

In normal recursion, you perform all recursive calls first, and calculate the result from return values at last (as show in the above example). Hence, you don’t get result until all recursive calls are made.

In tail recursion, calculations are performed first, then recursive calls are executed (the recursive call passes the result of your current step to the next recursive call). This makes the recursive call equivalent to looping, and avoids the risk of stack overflow.

Condition for tail recursion

A recursive function is eligible for tail recursion if the function call to itself is the last operation it performs.


Example 1

Not eligible for tail recursion because the function call to itself n*factorial(n-1) is not the last operation.


Example 2

Eligible for tail recursion because function call to itself fibonacci(n-1, a+b, a) is the last operation.

To tell for the compiler to perform tail recursion in Kotlin, you need to mark the function with tailrec modifier.


Output
354224848179261915075

This program computes the 100th term of the Fibonacci series. Since, the output can be a very large integer, we have imported BigInteger class from Java standard library.

Here, the function fibonacci() is marked with tailrec modifier and the function is eligible for tail recursive call. Hence, the compiler optimizes the recursion in this case.

If you try to find the 20000th term (or any other big integer) of the Fibonacci series without using tail recursion, the compiler will throw java.lang.StackOverflowError exception. However, our program above works just fine. It’s because we have used tail recursion which uses efficient loop based version instead of traditional recursion.

Factorial Using Tail Recursion

The example to compute factorial of a number in the above example (first example) cannot be optimized for tail recursion.
Here’s a different program to perform the same task.


Output
Factorial of 5 = 120

The compiler can optimize the recursion in this program as the recursive function is eligible for tail recursion, and we have used tailrec modifier that tells compiler to optimize the recursion.

Questions

I hope the description was understandable and clear. But if you have still questions, then leave me comments below! 😉

Have a nice a day! 🙂

 


 

Follow and like us:
Click to rate this post!
[Total: 0 Average: 0]

Leave a Reply

Your email address will not be published. Required fields are marked *