A linear-recursion example

Here, we will write a Scala Application to demonstrate a linear recursion technique:

package com.packt.publishing.recursion 
 
object LinearRecursionApp extends App { 
 
  val list = List(1,2,3,4,5,6,7,8,9) 
 
  val list2 = linearRecursion(list) 
 
  println("Original List = " + list) 
  println("After Tail Recursion of List = " + list2) 
 
  def linearRecursion[A](l: List[A]): List[A] = l match { 
    case h :: tail => linearRecursion(tail) ::: List(h) 
    case Nil => Nil 
  } 
 
} 

When we run the preceding application, we can observe the following output:

Original List = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
After Linear Recursion of List = List(9, 8, 7, 6, 5, 4, 3, 2, 1)

Both Scala and Java support this kind of recursion. However, it has the following drawbacks:

• It uses more stack-frames for recursive calls (it needs one stack-frame for each recursive call)
• It consumes or requires more memory
• There may be a chance of getting StackOverflowError