Fun with Recursion using Kotlin Extension functions

Fibonacci in Nature

Kotlin extension functions have proved to be most useful as proved by the numerous kts libs that we, Android devs have been using.

Writing recursive functions also now looks really elegant with the extension functions.

Just a quick background, for recursion we need a base condition which prevents the the recursion from being called indefinitely.

Let us see our omnipresent Recursive function , Factorial !

Here our base condition is if(number == 0 OR number == 1) return 1

fun Int.Factorial() : Long {
    return if(this == 0 || this == 1) {
        1
    } else this * (this-1).Factorial()
}

Now calling, this is as Simple as, 10.Factorial()

Thats it!

Now let us look at another example, Tree traversal.

Let us define Tree node entity and Binary Tree Entity

Here our base condition is encountered whenever a node is null.

class TreeNode(val key : Int) {
    var leftNode: TreeNode? = null
    var rightNode: TreeNode? = null
}

// Binary tree will have a root node 

class BinaryTree {
    var root: TreeNode? = null
}

for brevity the traversals algorithms are defined as follows -

INORDER [Left,Visit,Right] , PREORDER [Visit,Left,Right], POSTORDER [Left,Right,Visit]

Now let us translate this to Extension functions

fun TreeNode.Inorder() {
    this.leftNode?.Inorder()
    print("$key  ")
    this.rightNode?.Inorder()
}

fun TreeNode.Preorder() {
    print("$key  ")
    this.leftNode?.Preorder()
    this.rightNode?.Preorder()
}

fun TreeNode.Postorder() {

    this.leftNode?.Postorder()
    this.rightNode?.Postorder()
    print("$key  ")
}

No traversing is as simple as binaryTree.root.Inorder()

Example —

    val binaryTree = BinaryTree()
    binaryTree.root = TreeNode(1)
    binaryTree.root?.leftNode = TreeNode(2)
    binaryTree.root?.rightNode = TreeNode(3)
    binaryTree.root?.leftNode?.leftNode = TreeNode(4)
    binaryTree.root?.leftNode?.rightNode = TreeNode(5)

    println("Inorder ")
    binaryTree.root?.Inorder()
    println()
    println("Preorder ")
    binaryTree.root?.Preorder()
    println()
    println("Postorder ")
    binaryTree.root?.Postorder()


//This willprint out put as 
/*
Inorder
4  2  5  1  3
Preorder
1  2  4  5  3
Postorder
4  5  2  3  1 */

As always, code is available on github -

Please leave feedback, suggestions.