Skip to main content

Posts

Showing posts from July 23, 2017

Tail Recursion and Iteration

In the last session on linked list problems, we went over how to take a recursive function and transform the recursive call into a tail recursive one. The reason we do this is because tail recursive calls can be fairly straightforwardly optimized into a loop (and often automatically by a suitable compiler), thus removing any overhead from the recursive call. Regular recursive calls can get expensive in terms of space complexity if the recursion call stack gets deep, because the program needs to store information about the context for each recursive call. Recursion is a powerful tool of abstraction like any other. Functions on recursive data structures such as trees and linked lists lend themselves naturally to recursive solutions, and may be more readable and maintainable than their iterative counterparts. Thus, it is an important and even foundational concept to master. General Recursion The example we used was the reverse function which reverses a singly linked list. The straight…