Recursion
Table of Contents
.png)
1.
Session 2 (lab): Recursion
1.1.
Factorial, Power
Overview
Firstly, you will explore several traditional recursive methods to see their use and beahviour. Once the problem is analyzed, you will implement the solution with both iterative and recursive methods. Finally, you will compare these methods performance.
Problem analysis
A traditional linear-recursion example is to calculate the factorial of a positive integer n, represented as n!, consisting on multiplying the positive integers less than or equal to n:
Another well-known example is the power function, known as an and consists on repeatedly multiplying a n times:
The left-hand side of the figures shows the iterative version of the solution, while the right-hand side shows the recursive solution. Before starting to program, spend 2 minutes to analyze the figures and solutions presented.
Solution implementation
Now you are going to implement a Java class that calculates the factorial and power of integers. To do so, you will use a single class with a list of methods whose code will be filled throughout the exercise. Following code shows the structure of such class:
public class Functions {
public static int iterativeFactorial(int n) {
/* code here */
}
public static int recursiveFactorial(int n) {
/* code here */
}
public static int iterativePower(int base, int exponent) {
/* code here */
}
public static int recursivePower(int base, int exponent) {
/* code here */
}
public static void main(String args[]) {
/* Code to test the methods */
/* Code to compare both the iterative and recursive results */
}
}
-
Download and analyze the code. Answer to the following questions in a sheet of paper:
-
What is the purpose of using static methods in the code? Name a Java API class which follows the same design strategy.
-
Why doesn't this code compile? Before continue, solve the problem.
-
-
Implement the iterative solution to calculate the factorial of a number. You will have to implement the
iterativeFactorialcode, besides including in themainmethod the corresponding testing code. -
Implement the recursive solution to calculate the factorial of a number. Check its behaviour including the appropriate code into the
mainmethod. -
Repeat the two previous steps to calculate the power of a number. Do not forget to check its behavior inside the
mainmethod. -
You will have noticed that both the factorial and the power functions quickly reach high results, having the possibility of exceeding the limit for the
intdata type. How would you avoid the overflowing problems? (answer in writing) -
Compare the running times for the iterative and recursive solutions. To do so, you can use the
System.currentTimeMillismethod, which returns the time in milliseconds (in fact, it returns the difference between the current time and the time of the 1st of January of 1970, at 00:00, in milliseconds, have a look at it in the API). Call to this method just before and after calling the factorial or power function. The running time will be the difference between the two returned values. Is there any notable difference between the two implementations? Note: a good answer should be given in relative form (difference in percentage, %), not in absolute time.
1.2.
Fibonacci sequence
Description
It's a traditional recursive method to check its use and behaviour. The Fibonacci sequence is an endless sequence of natural numbers beginning with 0 and 1 and then each number is the result of the sum of the two preceding numbers. More information here. Implement a Java class that calculates the Fibonacci sequence up to a given number.
1.3.
Get the maximum item of an array
Description
The aim of the exercise is to write a recursive algorithm to get the maximum number located at an integer array.
1.4.
From integer to binary
In this exercise we are going to implement a class, called BinOperations, which must implement the interface Converter.java.
The expected functionality for the int2bin method is the following one: it accepts an integer as parameter and returns a String, which is a binary representation of the received integer. For the design of the solution, keep in mind the following figure:
Take special care with the following issues:
-
The method you are implementing accepts an integer, and returns a String object.
-
Despite there is an interative solution, your code must use recursion.
-
Do not consider negative values of int. Your code must control the allowed range of values for the input.
You can test your implementation with the following code:
public class BinOperationsTest {
public static void main(String args[]) {
Converter c = new BinOperations();
System.out.println("int2bin(1) = " + c.int2bin(1));
System.out.println("int2bin(2) = " + c.int2bin(2));
System.out.println("int2bin(3) = " + c.int2bin(3));
System.out.println("int2bin(4) = " + c.int2bin(4));
System.out.println("int2bin(5) = " + c.int2bin(5));
System.out.println("int2bin(6) = " + c.int2bin(6));
System.out.println("int2bin(7) = " + c.int2bin(7));
System.out.println("int2bin(8) = " + c.int2bin(8));
System.out.println("int2bin(9) = " + c.int2bin(9));
System.out.println("int2bin(10) = " + c.int2bin(10));
System.out.println("int2bin(25) = " + c.int2bin(25));
System.out.println("int2bin(256) = " + c.int2bin(256));
System.out.println("int2bin(2344) = " + c.int2bin(2344));
}
}
.png)
2.
Homework
2.1.
Palidromes
Description
A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words is generally permitted). A well known example could be "Was it a rat I saw?". As you can check the sequence of characters is the same in both reading directions. The aim of the exercise is to write a recursive algorithm to check if an String object is a palindrome.
2.2.
Mortgage payments
This exercise aims to recursively calculate mortgage payments.
According to "French Method", when the Bank lends a Capital (C), it is expected that, every month, the customer pays back a part of the capital, plus the interests due to the remaining capital.
So, every month (n) a constant payment is made, which is composed of interests and amortization M(n) = I(n) + A(n). Monthly interests I(n) = remCap(n) * r/12 , i.e. remaining capital multiplied by monthly interest rate. And Amortization A(n) is the difference between constant monthly payment and interests. The following month, remaining capital will have been reduced (Cp(n+1) = Cp(n)-A(n)), and the formula is applied again.
Program a class called Mortgage, which owns the method
int amortizationRecursive(int month, double capital, double rate, double fee)
Make the method prints the loan status every month:
"Month n: Remaining Capital=remCap(n) MonthlyPayment=M(n) Interests=I(n) Amortization=A(n)
For example, given a loan with initial capital of 100.000€, an annual interest rate of 3,5% and a constant monthly payment of 500€, when you call recursively that method, last lines should be similar to:
Month 300 -> Rem. Capital=796,10 MonthlyPayment=500,00 Interests=2,32 Amortization=497,68
Month 301 -> Rem. Capital=298,42 MonthlyPayment=299,29 Interests=0,87 Amortization=298,42
Remember: the recursion terminates when remaining capital is 0. Check also the possible error of setting a monthly payment lower than interests, since that would make impossible to pay the loan back.
WARNING: in a real mortgage, as those that we common citizens have, fixing the term and deducing the quota is more usual, while we hace fixed the quota and deduced the term (in comercial terms, it is more similar to a line of credit). Be careful if you apply this knowledge to your real life. You can find more information (in Spanish) here.
2.3.
ZIP-based Compression
The goal of this exercise is to create a ZIP file of a directory, recursively iterating through its structure to include the sub-directories. To do this, you will use the standard Java library whose classes allow to compress isolated files.
As a reference, and to focus on recursive aspects, we provide you with the needed code to compress a file with ZIP (see Compressor.java). The student must focus on implementing the dirFunc method, which iterates through a given directory structure and takes zipFunc method to the specific compressing tasks.