recursionis, when you may want to use it and when you really shouldn't, so that it is yet another tool in your problem-busting arsenal! The lesson will also briefly go over
stack overflow, an error that you may run into if you don't use
recursive function. A function that calls itself? Huh? That sounds like it could go on forever, and it can if you're not careful! For now, let us consider a very basic example of pseudocode (which should not be used in the real world) to demonstrate the concept:
sum_of_squaresto check if it's input is
equal to 1, and if so,
return 1. If this is not the case, We subtract 1 from the input and assign the value to
M. We then take the sum of our original input
Ntimes by iself, and the output of
sum_of_squareswith input M. So what will this look like? Let's find out:
evaluatethe result of the
original sum_of_squares(5), we must evaluate the result of the function underneath it. This is a very contrived example of a problem that you could easily work out with a loop, or some clever maths; but hopefully this will help introduce you to what recursion is.
large probleminto similar but
smaller chunksand using the solution to those chunks to solve the problem as a whole. The idea behind this rationale is that eventually you break the problem down into such small pieces that you can quickly arrive to an answer for that piece, and your answers stack up. This approach is commonly known as a
Divide and Conqueralgorithm.
In computer science, divide and conquer (D&C) is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
Stack Overflow. Yes, it does sound very familiar to a certain website you visit to solve all your programming problems!
Stack Overflow?To answer that, let's gloss over feature that languages use called
The Stack(not to be confused with a data structure we will cover in future!). Programs, regardless of the language, will make use of a finite section of reserved memory called
The Stackalso shares this section of memory with other features that programs use. Programs will take
functionsand place them on top of
The Stack, to be removed and used at a later time.
The Stackuntil such a point where no more recursive calls are being made; then you start removing previous calls from
The Stackand evaluating them.
Stack Overflowis when you're calling too many recursive functions without resolving them that
The Stackbecomes full and cannot store any more functions; and to prevent your program from spilling over and overwriting other important memory, your program stops and throws a
Stack Overflow?The first and most likely idea is to check that your function actually returns or stops when a certain condition has been met (like when N = 1 in our
sum_of_squarespseudo-code!). If your code never reaches it, you are going on forever! Like in our
sum_of_squarescode: If we set the original input as 0 or a negative number, the calls will never stop!