Introduction to recursive functions
In the introduction to functions' chapter we learned that, in computing, the definition of a function borrows the mathematical definition. We also learned that, much like in mathematics, a function can call another function. If you have wondered if a function can call itself, you were right and that's called recursion. The question about recursive algorithm's performance vs non recursive algorithms is not studied in this course, that is left for later disciplines. For now let's just focus on what is recursion and how to use it.
The logic of an recursive algorithm is pretty similar to the mathematical induction's logic. Depending on the class and the teacher, exercises about recursion are not studied or are, but very briefly. It's recommended that many exercises which can be solved both by recursive and iterative methods are done to learn well the concept. Optionally you can solve some exercises about mathematical induction to see the relationship between induction and recursion.
The basic logic is: see if a sequence's term can be expressed in function of another, for example an geometric or arithmetic progression, then we can write a recursive algorithm. In other words: if the next step can be expressed in function of the previous one or one of the previous, then we can convert an iterative algorithm to a recursive algorithm.
Errors of logic:
- Confuse iteration with recursion;
- Confuse a function that calls itself with calling a function with itself as an argument;
- Infinite or excessive recursion.
What comes below requires knowledge about functions
