BBS 516

Recursion and Multi Dimensional Arrays

Recursion
(Özyineli)
Recursion
• Recursion is all about breaking a big problem into smaller
occurrences of that same problem.
• Each person can solve a small part of the problem.
• What is a small version of the problem that would be easy to answer?
• What information from a neighbor might help me?
Recursive Algorithm
• Number of people behind me:
• If there is someone behind me,
ask him/her how many people are behind him/her.
• When they respond with a value N, then I will answer N + 1.

• If there is nobody behind me, I will answer 0.

Recursion
• Consider the following method to print a line of * characters:

// Prints a line containing the given number of

stars.
// Precondition: n >= 0
void printStars(int n) {
for (int i = 0; i < n; i++) {
System.out.print("*");
}
System.out.println("\n"); // end the line
of output
}

• Write a recursive version of this method (that calls itself).

• Solve the problem without using any loops.
• Hint: Your solution should print just one star at a time.
A basic case
• What are the cases to consider?
• What is a very easy number of stars to print without a loop?

void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else {
...
}
}
Handling more cases
• Handling additional cases, with no loops (in a bad way):

void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else if (n == 2) {
System.out.print("*");
System.out.println("*");
} else if (n == 3) {
System.out.print("*");
System.out.print("*");
System.out.println("*");
} else if (n == 4) {
System.out.print("*");
System.out.print("*");
System.out.print("*");
System.out.println("*");
} else ...
}
Handling more cases 2
• Taking advantage of the repeated pattern (somewhat better):

void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else if (n == 2) {
System.out.print("*");
printStars(1); // prints "*"
} else if (n == 3) {
System.out.print("*");
printStars(2); // prints "**"
} else if (n == 4) {
System.out.print("*");
printStars(3); // prints "***"
} else ...
}
Using recursion properly
• Condensing the recursive cases into a single case:

void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
} else {
// recursive case; print one more star
System.out.print("*");
printStars(n - 1);
}
}
Even simpler
• The real, even simpler, base case is an n of 0, not 1:

void printStars(int n) {
if (n == 0) {
// base case; just end the line of output
System.out.println();
} else {
// recursive case; print one more star
System.out.print("*");
printStars(n - 1);
}
}
Recursive tracing
• Consider the following recursive method:

int mystery(int n) {
if (n < 10) {
return n;
} else {
int a = n / 10;
int b = n % 10;
return mystery(a + b);
}
}

• What is the result of the following call?

mystery(648)
A recursive trace
mystery(648):
§ int a = 648 / 10; // 64
§ int b = 648 % 10; // 8
§ return mystery(a + b); // mystery(72)
mystery(72):
§ int a = 72 / 10; // 7
§ int b = 72 % 10; // 2
§ return mystery(a + b); // mystery(9)

mystery(9):
§ return 9;
Recursive tracing 2
• Consider the following recursive method:
int mystery(int n) {
if (n < 10) {
return (10 * n) + n;
} else {
int a = mystery(n / 10);
int b = mystery(n % 10);
return (100 * a) + b;
}
}

• What is the result of the following call?

mystery(348)
A recursive trace 2
mystery(348)
§ int a = mystery(34);
• int a = mystery(3);
return (10 * 3) + 3; // 33
• int b = mystery(4);
return (10 * 4) + 4; // 44
• return (100 * 33) + 44; // 3344

§ int b = mystery(8);
return (10 * 8) + 8; // 88

• return (100 * 3344) + 88; // 334488

• What is this method really doing?

Factorial Function
• n! = n * (n −1)* (n − 2)*... * 2 *1 for any integer n>0
0! = 1

• Iterative Definition:
•
int fval=1;

for(i=n; i>=1; i--)

fval = fval*i;
Factorial Function
Recursive Definition
• To define n! recursively, n! must be defined in terms of the factorial of
a smaller number.

• Observation (problem size is reduced):

n! = n * (n −1)!
• Base case:

0! = 1

• We can reach the base case by subtracting 1 from n if n is a positive

integer.
Factorial Function
Recursive Definition
Recursive definition
n! = 1 if n = 0
n! = n * (n −1)! if n > 0
int fact(int n)
{

if(n=0)
return (1);
else
return (n*fact(n-1));
}

This fact function satisfies the four criteria of a recursive solution.

Four Criteria of a Recursive Solution
Fibonacci Sequence
• It is the sequence of integers:
t0 t1 t2 t3 t4 t5 t6

0 1 1 2 3 5 8 ...

• Each element in this sequence is the sum of the two

preceding elements.
• The specification of the terms in the Fibonacci sequence:

n if n is 0 or 1 (i.e. n < 2)
tn =
tn−1 + tn−2 {otherwise
Fibonacci Sequence
• Iterative solution
int Fib(int n)
{

int prev1, prev2, tem, j;

if(n==0 || n==1)
return n;
else{
prev1=0;
prev2=1;
for(j=1;j<=n;j++)
{
temp = prev1+prev2;
prev1=prev2;
prev2=temp;
}
return prev2;
}
}
Fibonacci Sequence
• Recursive solution
int fibonacci(int n)
{

if(n<2)
return n;
else
return (fibonacci(n-2)+fibonacci(n-1));
}
MULTI DIMENSIONAL ARRAYS
Definition of a Multidimensional Array
• One-dimensional arrays are linear containers.
[0] [1] [2]

Multi-dimensional Arrays
[2]
[1]
[0]
[0] [1] [2] [3]
[0] [0]

[1] [1]

[2] [2]
[3]
[0] [1] [2] [3] [4]
Multidimensional Arrays
• Array declarations
• int a[10][3][2];
• “an array of ten arrays of three arrays of two ints”
• In memory
3 3 3

...

2 2 2 2 2 2 2 2 2

10

Seagram Building, Ludwig

Mies van der Rohe,1957
Storage Allocation
Array size

• In a matrix which is defined as

a[upper0] [upper1]…[uppern-1],
the number of items is:

Example: What is the number of items in a[20][20][2]?

= 20* 20 *2
Memory Storage
• There are two types of placement for multidimensional
arrays in memory:
• Row major ordering
• Column major ordering

Example: In an array which is defined as A[upper0][upper1], if the

memory address of A[0][0] is α, then what is the memory address of
A[i][0] (according to row major ordering)?
Memory Storage
• There are two types of placement for multidimensional
arrays in memory:
• Row major ordering
• Column major ordering

Example: In an array which is defined as A[upper0][upper1], if the

memory address of A[0][0] is α, then what is the memory address of
A[i][0] (according to row major ordering)?

= a + i x upper1 x sizeof(type)
 Memory Storage
•For a three-dimensional array A[upper0][upper1][upper2]
what is the memory storage like?

• Example: int y[2][2][4]

which slice? which row? which column?

• What is the memory address of y[1][1][3] if the memory

address of y[0][0][0] α?
Memory Storage
•For a three-dimensional array A[upper0][upper1][upper2]
what is the memory storage like?

• Example: int y[2][2][4]

which slice? which row? which column?

• What is the memory address of y[1][1][3] if the memory

address of y[0][0][0] α?
• a + (1*2*4 + 1*4 + 3 ) *4
Memory Storage
The memory address of a[i][0][0] is:
α + i * upper1 * upper2 *size

if the memory address of a[0][0][0] is α. Therefore, the

memory address of a[i][j][k] becomes:
α +(i * upper1 * upper2 + j * upper2 + k )*size
The memory address of a[i0] [i1] [i2]…[in-1] is:
% n−1
n−1 '' a j = ∏ upperk 0 ≤ j ≤ n −1
α + ∑i j a j & k= j+1
j=0 '
'( an−1 = 1