Introduction To Recursion
June 14, 2017
Recursion is a fundamental technique used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.
In computer science, a common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is Dynamic Programming. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached.
Mathematical Induction
It’s recommended that you learn mathematical induction before learning recursion. You can find our tutorial here:
If you are familiar with mathematical induction, recursion would be very simple.
Video
This video makes one of the best introductions into recursion, it’s a part of the course CS50 taught in Harvard university. If you don’t have a previous knowledge of recursion, then this is perfect video to watch.
Tutorial
However, if you still prefer text editorials, here is a nice one from Topcoder. An Introduction to Recursion, Part 1 – topcoder
After you feel that you are done with this introduction video/text (Or if you had previous experience with recursion), get yourself started and try our recursion quizzes which are made to refine your understanding and ensure that you are ready to start the serious business (Learning Dynamic Programming, Writing Backtracking solutions, etc).
Quizzes
Quizzes on recursion on CommonLounge :