To program a recursion, you need to think in recursion first. This programming skill is adjustable in sort of theoretical form. That is why in some case it makes it complicated in terms of designing a recursive algorithm.
To naturally grasp the concept of recursion in terms of its behavior or goal, let’s start by taking it as analogous or resembling to unrolling and rolling a toilet paper (can’t think of other objects).
 |
| Photo by Brandon Blinkenberg, CC BY 2.5, Link |
This phenomenon could attribute recursion that works by a forward and backward phase. Forward is the unrolling of toilet paper while backward is the rolling back. These phases are further discussed in the main steps provided to elevate your recursive mindset and apply your thoughts as an algorithm.
- Analyze the behavior of solving the problem naturally This is the pre-recursive stage to reflect the problem requirements in recursion. You can plan this with a scratch paper or you start by thought simulating the problem. In this article, our sample problem will be getting the factorial of a number. Factorials work by taking the number in succeeding decremented values by 1, limiting to 0 and multiply them to get the product of factorial. Example is the factorial of 4 or mathematically written as 4! leads to 4 x 3 x 2 x 1 = 24. To implicate a recursive solution to this sample problem, we know that we physically solve it by decrementing 1 from n until it reaches 1 and start multiplying them. Echoing the mentioned phrase “until it reaches 1” is already the condition that acts as the ‘stopper’ (not base case yet) of the recursion.
- Simpler, smaller versions of the problem From the nature of the sample problem, its solving behavior has a limiting factor to get to the solution just as other recursive problems. The process of limiting factor directs to the requirement of recursion which solves the problem by reducing it to simpler versions of itself. By the means of simpler versions, it is the smaller version of the problem environment from some minimal requirements by passing in a smaller value/parameter to be processed. For example, succeeding simpler versions of the problem 4! are 3!, 2!, and next smaller values. These became smaller or simpler because they are subtracted by 1 each time, which is the limiting factor. For the sample, let’s pre-process factorial of 4 by gathering the values in succeeding versions by the limiting factor, which in the case is subtraction by 1.
- Establish required base cases Finding the stopper doesn’t arrive yet to the base case of the recursion but finally leads to it. It is already stated that the simplest version implicates the base case. We see that the simplest version of factorials is 0!, representing 0 as the minimal input.
- Structure general case General case can be placed somewhere from block of statements that digests the problem matter to lead to the base case. The recurring function to be called can be located somewhere from the general case. For the sample, we refer back from the figure above where 4 x 3 x 2 x 1 is equivalent to 4 x 3!. This logic of factorial can associate a single code of statement which includes the number (parameter value) to be multiplied next to the recursive function call that returns succeeding value from the recurring calls. Since the general case has no other pre or post statements to execute, the general case for the problem is direct to n x (n-1)!.
- Backtrack successive versions of the problem Arriving to a base case while plotting in paper or thought simulating will logically return the value that will answer the preceding calling functions. To better picture your idea, it’ll be easier to simulate the backtracking of preceding function calls on scratch than in mind and assume solving backwards the computations for function calls as you trace back the preceding called functions bounded in its general case. This is the backward phase or computation phase where the values of preceding versions are computed by a process. The process can be an operation or set of statements. In the sample, multiplication derives factorials so the version values interact by multiplying with each other.
This is the forward phase or collective phase which describes recursive calls to process and gather successive simpler values that will be computed sooner. Collective because values from succeeding versions of the recursion are preserved for later computation while going forward in recursive calls.
To better understand the relations of simpler versions, let’s say the simplest version of a factorial problem is 0! which gives a solution of 1. This simplest version acts as already the base case for the problem. When we get to these versions, we see that if 4 itself is multiplied to 3!, it also leads to the answer of 4! which is 24 because 3! is equivalent to 3 x 2 x 1. This also applies to its next smaller versions. Quick saying that the answers from smaller versions are computed to preceding recurring functions.
As of the base case of the sample, when the parameter value is finally equal to 0, this returns value of 1 as 0! equals 1. The calling function receives the value and computed with its statements in the general case. The computed value will be returned from another underlying recursive function that precedes and continues until the first preceding function finishes its call and returns the final value.
 |
| Figure referred from book of D.S. Malik |
Note: fact() is the function name used for processing factorial
This article is loosely based from the book ‘Java Programming: From Problem Analysis to Program Design’ by D.S. Malik. You can head over this link to buy the book or look from your local bookstores and learn about Java.
Based on you, how do think recursively to solve a problem?
scszvzd
ReplyDelete