No need to know the end: recursion algorithm and mathematical induction

W hen I learned mathematical induction and solving a linear system using linear algebra for the first time, they seemed so magical to me and I felt like Neo who finally sees the matrix in the movie, The Matrix.

It has been years since I have learned them (don’t ask me how many years it has been, I do not want you to guess my age ) but I remember clearly that I was thinking that I understand the mind of a computer and how the world works for very short time — I can solve multiple linear equations at once and I can prove the existence of a pattern in a system. I will tell you how mathematical induction works very soon (and hopefully you can feel like Neo for a second) but let me tell you this first. When I have learned about a recursive algorithm recently, it reminded me of the time I learned mathematical induction. So magical and smart! Whenever I get these magical techniques that blow my mind, I make sure to dissect them until I know how they work. In this article, I would like to share with you what similarities I found between a recursive algorithm and mathematical induction and how they help me to implement the algorithm.