Recursion–Functions–STRUCTURED PROGRAMMING Course Notes

Recursion

• A recursive function calls itself, either directly or indirectly.
• A recursive function knows how to solve only the simplest case(s), or so-called base case(s). If the function is called with a base case, the function simply returns a result.
• If the function is called with a more complex problem, the function typically divides the problem into two conceptual pieces–a piece that the function knows how to do, and a piece that it does not know how to do. To make recursion feasible, the latter piece must resemble the original problem, but be a slightly simpler or slightly smaller version of it.
• For recursion, to terminate, the sequence of recursive calls must converge on the base case.
• Fibonacci Series is an example using recursion.
• The ratio of successive Fibonacci numbers converges on a constant value of 1.618…. This number frequently occurs in nature and has been called the ‘golden ratio’ or the golden mean.
• The Fibonacci series begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.
  • Ex: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
• The series occurs in nature and, in particular, describes a form of spiral. Humans tend to find the golden mean/ratio aesthetically pleasing.

Recursion vs. Iteration

• Iteration & recursion have many similarities: both are based on a control statement, involve repetition, involve a termination test, gradually approach termination and can occur infinitely.
• Recursion repeatedly invokes the mechanism, and consequently the overhead, of function calls. This can be expensive in both processor time & memory space. Each recursive call causes another copy of the functions variables to be created; this can consume considerable memory.

Notes:

Recursion–a function that calls itself. (i.e., Using the function inside its own function body.

Base case–an ending point for our function; whenever a function uses itself inside of itself, we need an end point, or a base case. The base case is like the end game that helps solve the broader puzzle (of the function calling itself). Creating a base case helps prevent the recursive function from running indefinitely. (i.e. crashing).

Recursive function is using the function inside the function body itself. And, remember, whenever we do this, we need to have a base case, we need to have an ending point that actually answers that question.

Recursion is sort of like function back-tracking; In the process of recursion, a function is called within another function (of itself) for multiple numbers of times.