Scribd
Upload
6 views14 pages

Converting Non-Tail to Tail Recursion

Here are the key steps to convert the recursive perm procedure to an iterative procedure: 1. Use an explicit stack to simulate the recursion stack 2. Push the initial call parameters (M, rows, cols) onto the stack 3. In a while loop, pop the top frame from the stack 4. If the base case is reached, calculate and return the result 5. Otherwise, make the recursive calls by pushing frame parameters onto the stack 6. After the recursive calls return, perform the remaining computation and return/push result This replaces the implicit call stack with an explicit one, eliminating recursion. Local variables track state instead of being passed recursively.

Uploaded by

AKSHAT JAIN
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
6 views14 pages

Converting Non-Tail to Tail Recursion

Here are the key steps to convert the recursive perm procedure to an iterative procedure: 1. Use an explicit stack to simulate the recursion stack 2. Push the initial call parameters (M, rows, cols) onto the stack 3. In a while loop, pop the top frame from the stack 4. If the base case is reached, calculate and return the result 5. Otherwise, make the recursive calls by pushing frame parameters onto the stack 6. After the recursive calls return, perform the remaining computation and return/push result This replaces the implicit call stack with an explicit one, eliminating recursion. Local variables track state instead of being passed recursively.

Uploaded by

AKSHAT JAIN
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

CS/IS F211 Data Structures & Algorithms

2/3/2018
Sundar B.
REVIEW: TOP DOWN DESIGN

CSIS, BITS, Pilani


Space Complexity:
Recursion vs. Iteration:
1
Tail Recursion and Tail Recursion Elimination
Eliminating Non-Tail Recursion using an explicit Stack
2/3/2018
Sundar B.
CONVERTING NON-TAIL RECURSIVE PROCEDURES TO
TAIL RECURSIVE PROCEDURES

CSIS, BITS, Pilani


2
NON-TAIL RECURSIVE FUNCTIONS - EXAMPLE
 Consider the following procedure for computing the length
of a linear linked list:
length(LinkedList ls)
{
if (ls != null) {
return 1 + length(ls->next);
} else
return 0;
}

This is a non-tail (recursive) call.

3
CONVERTING NON-TAIL RECURSION TO TAIL RECURSION - EXAMPLE
 Consider the following procedure for computing the length
of a linear linked list:
length(LinkedList ls)
{ return len(ls, 0); }

len(LinkedList ls, int acc)


{
if (ls != null) {
return len(ls->next, 1+acc);
} else
return acc;
}
This is a tail (recursive) call.

How and why does this work?


4
CONVERTING NON-TAIL RECURSION TO TAIL RECURSION - VISUALIZATION
How and why does this work?
Visualize the variable length(LinkedList ls)
acc(umulator) as a stack: { return len(ls, 0); }
• We push a 0 first (we are yet
to see a node). len(LinkedList ls, int acc)
• For every node, we push a {
+1 if (ls != null) {
• When the list is null, we return len(ls->next, 1+acc);
must add all the +1s (and } else
return the value). return acc;
}

// S is a global stack
length(LinkedList ls) { push(S, 0); len(ls); countStk(S); }
len(LinkedList ls) {
if (ls != null) {push(“+1”); len(ls->next); }
5
} else return;
}
VISUALIZATION OF LENGTH OF LINKED LIST
CountStk must add all the “+1”s
pushed on stack: length(LinkedList ls)
but we realize { return len(ls, 0); }
addition is commutative and
associative i.e. len(LinkedList ls, int acc)
we can reverse the sequence of {
additions: if (ls != null) {
• Initialize a counter (on return len(ls->next, 1+acc);
stack); } else
• For every node: pop it, add return acc;
+1, push it back }
• at the end return it.

// S is a global stack
length(LinkedList ls) { push(S, 0); len(ls); countStk(S); }
len(LinkedList ls) {
if (ls != null) {push(“+1”); len(ls->next); } 6
} else return;
}
CONVERTING NON-TAIL RECURSION TO TAIL
RECURSION

2/3/2018
 Does the method employed in converting length
generalize?

Sundar B.
 (Try to) convert the following procedures (into tail-recursive
form):
 fact(N) { if (N==0) return 1; else return N*fact(N-1); }

CSIS, BITS, Pilani


 inSort(Ls, N) { if (N<=1) return;
 else { inSort(Ls, N-1);
 insertInOrder(Ls, N-1, Ls[N-1]);
 }

7
2/3/2018
Sundar B.
CONVERTING NON-TAIL RECURSIVE PROCEDURES TO
ITERATIVE PROCEDURES USING EXPLICIT STACK

CSIS, BITS, Pilani


8
NON-TAIL RECURSIVE PROCEDURE - EXAMPLE

2/3/2018
 Consider a (square) matrix where:
 each row is sorted in increasing order

Sundar B.
 each column is sorted in increasing order

Let us refer to this as a semi-ordered matrix.


 Problem:
 Given a semi-ordered matrix M of dimensions N*N, and a

CSIS, BITS, Pilani


value V , locate V if it is present in M.

9
DIVIDE-AND-CONQUER DESIGN: SEMI-ORDERED MATRIX

2/3/2018
 Analogous to binary search:
 Divide M[loRow..hiRow][loCol..hiCol] along each dimension:

Sundar B.
 i.e. consider sub-matrices:

 M[loRow..midRow][loCol..midCol]

 M[loRow..midRow][midCol+1..hiCol]

 M[midRow+1..hiRow][loCol..midCol]

CSIS, BITS, Pilani


 M[midRow+1..hiRow][midCol+1..hiCol]

 Which of these should be searched?


 compare V with M[midRow,midCol]
 V==M[midRow,midCol] : return (midRow,midCol)

 V<M[midRow,midCol]: ??

 V>M[midRow,midCol] : ??
10
RECURSIVE ALGORITHM: FIND IN A SEMI-ORDERED MATRIX
 // Precondition: M is square
 matfnd(M,lr,hr,lc,hc,V) {

2/3/2018
 if (lr>hr) return (-1,-1);
 mr=(lr+hr)/2; mc=(lc+hc)/2;

Sundar B.
 if (V==M[mr,mc]) return (mr,mc);
 else if (V<M[mr][mc]) { // discard the right bottom quadrant
 res = matfnd(M,lr,mr,lc,mc,V);

 if (res!=(-1,-1)) return res; else res = matfnd(M,lr,mr,mc+1,hc,V);

CSIS, BITS, Pilani


 if (res!=(-1,-1)) return res; else return matfnd(M,mr+1,hr,lc,mc,V);

 } else { // discard the left top quadrant


 res = matfnd(M,mr+1,hr,mc+1,hc,V);

 if (res!=(-1,-1)) return res; else res = matfnd(M,lr,mr,mc+1,hc,V);

 if (res!=(-1,-1)) return res; else return matfnd(M,mr+1,hr,lc,mc,V);

 }
Which of the recursive
 } 11
calls are tail calls?
ALGORITHM: FIND IN A SEMI-ORDERED MATRIX
matfnd(M,lr,hr,lc,hc,V) {
while(lr<=hr) {
mr=(lr+hr)/2; mc=(lc+hc)/2;
if (V==M[mr,mc]) return (mr,mc);
else if (V<M[mr][mc]) { // discard the right bottom quadrant
res = matfnd(M,lr,mr,lc,mc,V);
if (res!=(-1,-1)) return res; else res = matfnd(M,lr,mr,mc+1,hc,V);
if (res!=(-1,-1)) return res; else { lr=mr+1; hc=mc; }
} else { // discard the left top quadrant
res = matfnd(M,mr+1,hr,mc+1,hc,V);
if (res!=(-1,-1)) return res; else res = matfnd(M,lr,mr,mc+1,hc,V);
if (res!=(-1,-1)) return res; else else { lr=mr+1; hc=mc; }
}
}
return (-1,-1);
} Tail Recursion has been eliminated! 12
ITERATIVE ALGORITHM: FIND IN A SEMI-ORDERED MATRIX
matfnd(M,lr,hr,lc,hc,V) { // S is a stack
S = push(S,(lr,hr,lc,hc));
while (!isEmpty(S)) {
(lr,hr,lc,hc) = top(S); S = pop(S);
while(lr<=hr) {
mr=(lr+hr)/2; mc=(lc+hc)/2;
if (V==M[mr,mc]) return (mr,mc);
else if (V<M[mr][mc]) { // discard the right bottom quadrant
S = push(push(S,(lr,mr,lc,mc)),(lr,mr,mc+1));
lr=mr+1; hc=mc;
} else { // discard the left top quadrant
S = push(push(S,(mr+1,hr,mc+1,hc)),(lr,mr,mc+1,hc));
lr=mr+1; hc=mc;
}
}
return (-1,-1); 13

}
RECURSION TO ITERATION: PERMANENT OF A MATRIX

2/3/2018
perm(Matrix M, rows, cols)
{

Sundar B.
for (j=0, pm=0; j<rows; j++) {
pm += M[0,j]*perm(minor(M,rows,cols,0,j));
}
}

CSIS, BITS, Pilani


Exercise:
Convert the recursive procedure perm to an iterative procedure.

14

You might also like