[go: up one dir, main page]
Scribd
Upload
20 views4 pages

Lab#03

Uploaded by

maazhoney2243
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views4 pages

Lab#03

Uploaded by

maazhoney2243
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Lab#03 Recursion SSUET/QR/114

LAB # 03

RECURSION

OBJECTIVE: To understand the complexities of the recursive functions and a way to


reduce these complexities.

What is Recursion?

An algorithm is recursive if it calls itself to do part of its work.


In general, a recursive algorithm must have two parts: the base case, which handles a
simple input that can be solved without resorting to a recursive call, and the recursive
part which contains one or more recursive calls to the algorithm where the parameters
are in some sense ―closer‖ to the base case than those of the original call.

A recursive function is defined in terms of base cases and recursive steps.

 In a base case, we compute the result immediately given the inputs to the function.
 In a recursive step, we compute the result with the help of one or more recursive
calls to this same function, but with the inputs somehow reduced in size or
complexity, closer to a base.

Memoization

Memoization ensures that method does not execute more than once for same inputs by
storing the results in the data structure(Usually Hashtable or HashMap or Array).

Implementation
Let’s understand with the help of Fibonacci example. Below is a sample of fibonacci
series.

0,1,1,2,3,5,8,13,21,34,55,89,144….

So it has recurrence relation of:

F(n)= F(n-1)+F(n-2)

the recurrence fuction will be;

// Fibonacci without Memoization


public int fibonacci(int n){

if( n == 0 ) return 0;
if( n == 1 ) return 1;
System.out.println("Calculating fibonacci number for: "+n);
return (fibonacci(n-1) + fibonacci(n-2));

SE-203L Data Structures & Algorithms


Lab#03 Recursion SSUET/QR/114

Fig.1 A recursive tree for fibonacci series with n=5

If you notice here, we are calculating f(3) twice and f(2) thrice here, we can avoid
duplication with the helping of caching the results. We will use one instance variable
memoizeTable for caching the result.
Check if n is already present in memoizeTable, if yes, return the value
If n is not present in memoizeTable, then compute and put the result in memoizeTable.

Sample Program#1

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoizationAlgorithm {

private Map<Integer, Integer> memoizeTable = new HashMap<>(); // O(1)

// Fibonacci with Memoization


public int fibonacciMemoize(int n){

if( n == 0 ) return 0;
if( n == 1 ) return 1;

if( this.memoizeTable.containsKey(n) )
{
System.out.println("Getting value from computed result for "+n);
return this.memoizeTable.get(n);
}

int result = fibonacciMemoize(n-1)+ fibonacciMemoize(n-2);


System.out.println("Putting result in cache for "+n);

SE-203L Data Structures & Algorithms


Lab#03 Recursion SSUET/QR/114

this.memoizeTable.put(n, result);

return result;

// Fibonacci without Memoization


public int fibonacci(int n){

if( n == 0 ) return 0;
if( n == 1 ) return 1;

System.out.println("Calculating fibonacci number for: "+n);


return (fibonacci(n-1) + fibonacci(n-2));
}

public static void main(String[] args) {

FibonacciMemoizationAlgorithm fibonacciAlgorithm = new


FibonacciMemoizationAlgorithm();
System.out.println("Fibonacci value for
n=5: "+fibonacciAlgorithm.fibonacciMemoize(5));

}
}

You can see, we are not computing fibonacci number for 2 and 3 more than once.

LAB TASK

1. Write a program which takes an integer value (k) as input and prints the sequence of
numbers from k to 0 in descending order.

2. Write a program to reverse your full name using Recursion.

3. Write a program to calculate the sum of numbers from 1 to N using recursion. N


should be user input.

4. Write a recursive program to calculate the sum of elements in an array.

5. Write a recursive program to calculate the factorial of a given integer n

6. Write a program to count the digits of a given number using recursion.

SE-203L Data Structures & Algorithms


Lab#03 Recursion SSUET/QR/114

HOME TASK

1. Write a java program to find the N-th term in the Fibonacci series using Memoization.

2. Write a program to count the digits of a given number using recursion.

3. Write a java program to check whether a given string is a palindrome or not. A


palindrome is a string that reads the same forwards and backwards.Print "YES" if the
string is a palindrome, otherwise print "NO".

4. Write a recursive program to find the greatest common divisor (GCD) of two
numbers using Euclid's algorithm.

SE-203L Data Structures & Algorithms

You might also like