Recursion

Recursion

Throughout the last few weeks we have encompassed most of the introduction to recursion via multiple worked and traced example functions in class and during the tutorials.

Recursion allows programmers to write functions that run much faster. The problem that the programmer is trying to solve is broken down from its most complex version into sub-problems and so forth until the function arrives to a base case.

Henceforth, in order to write a recursive function, one has to identify what the base case is (e.g. in what case will the function be run at is simplest form) and place it in the code written under (or for) the 'else' statement. Furthermore, in order to write the function, the programmer has to identify how the values returned by the function for each value of the function's parameter are related. E.g. for a function f(x:int)-> int: what is the relationship between f(2) and f(3) and how do I find f(3) if I already have f(2). After that, the programmer needs to identify what will be the value that will change every time, the iterator that will get make the recursive function reach its base case after a while. For example:

in this case the iterator is i. it permits the function to run through all the possible elements in a nested list. The base case is when there are no more nested depths to the list currently being iterated over. When this case is reached the function simply finds the values that are equal to 3 and deletes them. If there is a list inside a list, the function will recursively enter all of them by calling itself until there are no more and the base case is reached.

Although recursion may seem complex at first for most programmers. Once one wraps his/her head around it, it makes the programmer's life much easier and allows him/her to write programs that are much more efficient and powerful.