One Pager Cheat Sheet

• Both iteration and recursion can be used to solve programming problems, but an important thing to keep in mind is that for any problem that can be solved via iteration, there is a corresponding recursive solution and vice versa.
• Iteration is the repetition of a block of code using control variables or a stopping criterion, typically in the form of for, while or do-while loop constructs.
• A recursive function is one that calls itself, such as the printList function which uses the divide and conquer principle to print the numbers 1 to 5.
• The printList function implements recursion by defining a base case (the non-recursive part) and a general / recursive case (defining how to solve the problem in terms of a smaller version of itself).
• The execution of a recursive function without a base case will not raise an exception, but can lead to stack overflow if the maximum number of recursive calls is exceeded.
• Recursion is a technique that enables a function to save its local variables and parameters on an activation stack, which is then popped off when the function exits or the base case is reached.
• The printList function will print the values in reverse, 5, 4, 3, 2, 1, when the statements are reversed, which happens during the "unwind recursion" phase after the base case is invoked.
• We can calculate the factorial of a number using either an iterative or recursive implementation in C++.
• The iterative solution is more efficient for programming languages such as C++ or Java as it runs in constant memory, compared to the recursive solutions which generates 4 records on the activation stack for each call.
• The recursive version of the factorial function takes up more memory due to increased activation stack records, while being less optimal in languages like C++ and Java.
• Quick Sort is a naturally recursive sorting algorithm that divides the entire array into smaller pieces, and is conceptually easier to implement via recursion.
• The clear concept behind Quick Sort is easily understood from the elegant and simple recursive version of the algorithm, which adjusts elements around a pivot before calling quickSort recursively on both subarrays.
• We need to implement our own stack to maintain the indices of the left and right subarrays for the iterative version of quickSort.
• Of course, the main question now is: which solution to go for, iterative or recursive, and I would still advise you to go for the iterative solution to avoid segmentation faults while the recursive version is easier to write and understand.
• The Towers of Hanoi game is an example of a naturally recursive problem in which you move disks from one shelf to another while following a rule that a smaller disk cannot be placed on top of a larger disk.
• Break down the problem into a smaller version of itself to solve it recursively using an intermediate location when moving disks.
• The figure shows the Recursion Tree for the 3 disk Towers of Hanoi problem, with the final solution being derived from a direct translation of the pseudo-code in C++.
• We can solve the Towers of Hanoi problem using an iterative approach by pushing step 3, then 2 and then 1 onto a temporary stack.
• The number of recursive calls required to check if the number 37 is prime using recursion is three, due to the base case and subsequent checks for divisibility.
• Using an iterative technique instead of recursion can be more efficient when solving problems like Towers of Hanoi since there would be no overhead associated with the activation stack.
• Replace recursion with iteration by initializing an empty array, iterating through it with a loop, removing each element for processing, making the relevant calculations, and finally, adding it back to the array.