Skip to main content

Algorithm: Recursion

The idea of calling one function from another immediately suggests the possibility of a function calling itself. Recursion is a powerful general-purpose programming technique, and is the key to numerous critically important computational applications, ranging from combinatorial search and sorting methods that provide basic support for information processing to the fast Fourier Transform for signal processing.

Induction: a method of reasoning in which you use individual ideas or facts to give you a general rule or conclusion.

Reasoning: the process by which you reach a conclusion after thinking about all the facts.

Recursive programming is directly related to mathematical induction, a technique for providing facts about discrete functions. Proving that a statement involving an integer N is true for infinitely many values of N by mathematical induction involves two steps.
step 1: the base case is to prove the statement true for some specific value or values of N(usually 0 or 1).
step 2: the induction step is the central part of the proof. For example, we typically assume that a statement is true for all positive integers less that N, then use that fact to prove it true for N.

Examples,
1. N!
base case: N = 1. Returns a value without making any subsequent recursive calls. it does this for one or more special input values for which the function can be evaluated without recursion.

Induction step: N* factorial(N-1) and N decreases by one for each call, so the sequence of parameter values converges to the base case of N=1;

Converge: approach a limit as the number of terms increases without limit.


public static int factorial(int N) { 
   if (N == 1) return 1; 
   return N * factorial(N-1); 
} 

2. Towers of Hanoi
Rules:
Move only one disc a time.
Never place a disc on a smaller one.

 public static void solve(int first_disc, char aTower, char bTower, char cTower) {
        if (first_disc == 1) {
            System.out.println("Disk 1 on tower " + aTower + " moving to tower " + cTower);
        } else {
            solve(first_disc - 1, aTower, cTower, bTower);
            System.out.println("Disk " + first_disc + " on tower " + aTower + " moving to tower " + cTower);
            solve(first_disc - 1, bTower, aTower, cTower);
        }
    }


Comments

Popular posts from this blog

Stretch a row if data overflows in jasper reports

It is very common that some columns of the report need to stretch to show all the content in that column. But  if you just specify the property " stretch with overflow' to that column(we called text field in jasper report world) , it will just stretch that column and won't change other columns, so the row could be ridiculous. Haven't find the solution from internet yet. So I just review the properties in iReport one by one and find two useful properties(the bold highlighted in example below) which resolve the problems.   example:
<band height="20" splitType="Stretch"> <textField isStretchWithOverflow="true" pattern="" isBlankWhenNull="true"> <reportElement stretchType="RelativeToTallestObject" mode="Opaque" x="192" y="0" width="183" height="20"/> <box leftPadding="2"> <pen lineWidth="0.25"/> …

JasperReports - Configuration Reference

Live - solving the jasper report out of memory and high cpu usage problems

I still can not find the solution. So I summary all the things and tell my boss about it. If any one knows the solution, please let me know.


Symptom: 1.The JVM became Out of memory when creating big consumption report 2.Those JRTemplateElement-instances is still there occupied even if I logged out the system
Reason:         1. There is a large number of JRTemplateElement-instances cached in the memory 2.The clearobjects() method in ReportThread class has not been triggered when logging out
Action I tried:      About the Virtualizer: 1.Replacing the JRSwapFileVirtualizer with JRFileVirtualizer 2.Not use any FileVirtualizer for cache the report in the hard disk Result: The japserreport still creating the a large number of JRTemplateElement-instances in the memory     About the work around below,      I tried: item 3(in below work around list) – result: it helps to reduce  the size of the JRTemplateElement Object                Item 4,5 – result : it helps a lot to reduce the number of  JRTemplateE…