INT209 Data Structures

Recursion
Recursive Definitions
• Recursion
– Process of solving a problem by reducing it to smaller
versions of itself
• Recursive definition
– Definition in which a problem is expressed in terms of a
smaller version of itself
– A recursive definition has one or more base cases where
the recursion process will stop.

2
Recursive Definitions - ontinued
• Recursive Algorithm
– An algorithm that finds the solution to a given problem
by reducing the problem to smaller versions of
itself
– Has one or more base cases
– Implemented using recursive methods

• Recursive method
– Method that calls itself

3
Recursive Definitions - ontinued
• Base case
– A case in a recursive definition in which the solution is
obtained directly and stops the recursive process.
– Values of the input variables for which we perform no recursive
calls are called base cases (there should be at least one base
case).
– Every possible chain of recursive calls must eventually reach
a base case.

4
Recursive Definitions - continued
• General solution
– Breaks problem into smaller versions of itself
• General case
– Case in recursive definition in which a smaller
version of itself is called
– Must eventually be reduced to a base case

5
Example
• Classic example – the factorial function:
n! = 1· 2· 3· ··· · (n-1)· n

1 if n 
• Recursive definition: f (n)  0
 n  f (n
else
1)

6
Tracing a Recursive Method
• Recursive method
– Logically, you can think of a recursive method having
unlimited copies of itself
– Every recursive call has its own:
• Code

• Set of parameters
• Set of local variables

7
Designing Recursive Methods
• Understand problem requirements
• Identify base cases
• Provide direct solution to each base case
• Identify general case(s)
• Provide solutions to general cases in terms of smaller versions
of general cases

8
Recursive Factorial Method
public static int fact(int num)
{
if (num == 0)
return 1;
else
return num *
fact(num –
1);
}

9
Recursive Fibonacci

10
Recursive Fibonacci

public static int rFibNum(int a, int b,int n){

if (n == 1)
return a;
else if (n == 2)
return b;
else
return rFibNum(a, b, n -1) +
rFibNum(a, b, n - 2);
}

11
Recursive Fibonacci

12
Exercises
Class Exercise #1:
• Write a recursive function sumN(int n) that takes a
positive integer n and computes the sum:
1 + 2 +…+ n recursively.

13
Exercises
Class Exercise #1 Solution:
import java.util.*;
public class recursiveSumN {
public static void main(String args[])
{
int num = 6;
int sum;

sum = sumN(num);
System.out.println("Sum:
"+sum);

} // end of main

public static int sumN(int n)

{ if(n==0)
return 0;
else
return(n + sumN(n-1));
} 14
}// End of recursiveSumN
Exercises
Class Exercise #2:
• Write a recursive function sumN(int n) that takes a positive
integer n and computes the sum of odd integers between 0
and n:

15
Exercises
Class Exercise #2 Solution:
import java.util.*;
public class recursiveSumOdd {
public static void main(String args[]){
int num = 6;
int sum;
sum = sumOdd(num);
System.out.println("Sum of odd numbers:
"+sum);
} // end of main
public static int sumOdd(int n){
if(n==0)
return 0;
else
if(n%2 != 0)
return(n+sumOdd(n-1));
else
returnsumOdd(n-1);
}
}// End of recursiveSumOdd 16
Sum of Value in an Array
Sum of Value in an Array

public static int findArraySum(int[] dataArray, int length){

if(length==0)
return 0;
else
return(dataArray[length-1] + findArraySum(dataArray, length-1));

17
Sum of Value in an Array
import java.util.*;
public class recursiveArraySum {
public static void main(String args[]){
int[] data ={20, 12, 49, 33, 10, 4, 78, 66, 90, 56, 45, 28};
int arraySum=0;
arraySum = findArraySum(data, data.length);
System.out.println(“Array Sum: "+arraySum);
} // end of main

public static int findArraySum(int[] dataArray, int numElements){

if(numElements==0)
return 0;
else {
return
(dataArra
y[numElem
ents-1] +
findArray
Sum(dataA
rray,
numElemen
ts-1));
18
}
Sum of Value in an Array – Another version
public static int findArraySum2(int[] dataArray, int numElements, int currentSum){

if(numElements==0)

return currentSum;

else {

currentSum += dataArray[numElements-1];

return(findArraySum2(dataArray, numElements-1, currentSum));

19
Sum of Value in an Array – Another version
import java.util.*;
public class recursiveArraySum_2 {
public static void main(String args[]){
int[] data ={20, 12, 49, 33, 10, 4, 78, 66, 90, 56, 45, 28};
int arraySum=0;
arraySum = findArraySum2(data, data.length, arraySum);

System.out.println(“Array Sum: "+arraySum);

} // end of main

public static int findArraySum2(int[] dataArray, int numElements, int currentSum){

if(numElements==0)
return currentSum;
else {
currentSum += dataArray[numElements-1];
return(findArraySum2(dataArray, numElements-1, currentSum));
}

}// End of recursiveArrayMax_2 class

20
Largest Value in Array
Largest Value in Array
public static int findArrayMax(int[] dataArray, int numElements, int currentMax){

if(numElements==0)
return currentMax;
if(currentMax < dataArray[numElements-1])
currentMax = dataArray[numElements-1];
return(findArrayMax(dataArray, numElements-1,currentMax));

21
Largest Value in Array
import java.util.*;
public class recursiveArrayMax {

public static void main(String args[]){

int[] data ={20, 12, 49, 33, 10, 4, 78, 66, 90, 56, 45, 28};
int maxInitialValue = data[0];
int maxValue;

maxValue = findArrayMax(data, data.length, maxInitialValue);

System.out.println("Max value: "+maxValue);

} // end of main
public static int findArrayMax(int[] dataArray, int numElements, int
currentMax){
if(numElements==0)
return currentMax;
if(currentMax<dataArray[numElements-1])
currentMax = dataArray[numElements-1];
return(findArrayMax(dataArray, numElements-
1,currentMax));
}
}// End of recursiveArrayMax class 22
Largest Value in Array – Another Solution
import java.util.*;
public class recursiveArrayMax_2 {

public static void main(String args[]){

int[] data ={20, 12, 49, 33, 10, 4, 78, 66, 190, 56, 45, 120};
int maxValue;

maxValue = findArrayMax(data, data.length);

System.out.println("Max value: "+maxValue);

} // end of main

public static int findArrayMax(int[]

dataArray, int numElements){
if(numElements==0)
return dataArray[0];
if(dataArray[0] < dataArray[numElements-1])
dataArray[0] = dataArray[numElements-1];
return(findArrayMax(dataArray, numElements-1));
}

}// End of recursiveArrayMax class

23
Binary Search
• v

24
Binary Search

25
Binary Search
Graphical Example:

26
Binary Search

27
Recursion or Iteration?
• Two ways to solve particular problem
– Iteration
– Recursion

• Iterative control structures: use looping to repeat

a set of statements
• Tradeoffs between two options
– Sometimes recursive solution is easier
– Recursive solution is often slower
28
Class Exercise: Recursive sum of queue elements
public static int sumQueueElements(IntArrayQueue Q, int size) {
int num;
if(size==0)
return 0;
else {
num = Q.dequeue();
Q.enqueue(num);
return num+
sumQueueElements(
Q, size-1);
}
}//End of
sumQueueElements

29
Class Exercise: Recursive sum of queue elements
import java.util.*;
public class testRecSumQueueElements {
public static Scanner console = new Scanner(System.in);
public static void main(String[] args) {
IntArrayQueue myQueue = new IntArrayQueue(100);
int num;
System.out.print("Enter an integer value (-999 to stop): ");
num = console.nextInt();
while (!(num == -999))
{ myQueue.enqueue(num);
num = console.nextInt();
}
System.out.println(myQueue.toS
tring());
int qSum = sumQueueElements(myQueue, myQueue.size());
System.out.println("Sum of Queue Elements: " + qSum);
System.out.println("myQueue Elements: "+myQueue.toString());
} // End of main

public static int sumQueueElements(IntArrayQueue Q, int size) {

- - -
}//End of sumQueueElements
}// End of program class 30
Class Exercise: Recursive sum of list elements
public static int recSumList(SinglyLinkedList<Integer> list, int size){

int num;
if(size==0)
return 0;
else {
num=li
st.remove
First();
list.a
ddLast(nu
m);
return
(num +
recSumLis
t(list,
31
size-1));
Class Exercise: Recursive sum of list elements
import java.util.*;
public class testRecSumSinglyLinkedList {
static Scanner console = new Scanner(System.in);
public static void main(String[] args) {
int element;
SinglyLinkedList<Integer> myList = new
SinglyLinkedList<Integer>();
System.out.println("Enter element (-999 to stop): ");
element = console.nextInt();
while (!(element == -999))
{ myList.addLast(element);
element = console.nextInt();
}
// Print the elements of the list from first to last int
sumList = recSumList(myList, myList.size());
System.out.println("Sum of list elements: "+sumList);
myList.printList();
} // End of main
public static int recSumList(SinglyLinkedList<Integer> list, int size){
- - -
}
}// End of class 32
Class Exercise: Recursive sum of stack elements
public static int recSumStackElements(IntArrayStack S,
int size, IntArrayStack temp){
int element;
if(size == 0){
int sz=temp.size();
for(int i=0; i<sz; ++i)
S.push(temp.pop());
return 0;
}
else {
element = S.pop();
temp.push(element);
return element +
recSumStackElement
s(S, size-1, temp);
}
} //End of
recSumStackElements
Method
33
Class Exercise: Recursive sum of stack elements
public class testRecSumStackElements
{ public static void main(String[] args)
{
int[] num = {3, 7, 9, 5, 4, 12, 8, 15};
int i;
IntArrayStack myStack = new
IntArrayStack(num.length);
IntArrayStack tempStack = new
IntArrayStack(num.length);
for(i=0; i<num.length;++i)
myStack.push(num[i]);
System.out.println("Stack
content before calling
sum: " +
m
y
S
t
a
c
k
.
t
o 34
S