Subroutines and Control Abstraction
Outline
• Tail Recursion
• Tree Recursion
• Stack Smashing
Tail Recursion
• A tail-recursive function
– Is one in which additional computation never follows a recursive call, i.e., the return value is simply
whatever the recursive call returns.
• Dynamically allocated stack space is unnecessary
• The compiler can reuse the space belonging to the current iteration when it makes the
recursive call.
// Inherent Tail-Recursive Function
int gcd(int m, int n) {
if(n==0) return m;
return gcd(n, m%n); }
Tail Recursion Example
gcd (6, 0) R1 = 6
6, 0 gcd (12, 6) int gcd(int m, int n)
{
12, 6 gcd (18, 12)
if(n==0) return m;
18, 12 gcd (30, 18) return gcd(n, m%n); }
30, 18 main() x = gcd(30,18)
param x
Tail Recursion Example Cont..
gcd-IV - gcd (6,0)
gcd-III - gcd (12, 6)
gcd-II - gcd (18, 12) R1 = 6
gcd-I - gcd (30, 18) gcd-I - gcd (30, 18) gcd-I - gcd (12, 6) gcd-I - gcd (6,0)
main () - Stack main () - Stack frame for main () - Stack frame for main () - Stack frame for
frame for Caller Caller Caller Caller
Stack frame poped out for every call and the same space
is reallocated for a frame of the next recursive call
Recursive to Tail-Recursive Function
• Non-tail Recursive Function • Tail Recursive Function
• int fact(unsigned int n) { • int factorial (int n) { return fac (n,1) }
if (n == 0) return 1; int fac(int n, int a)
return n*fact(n-1); } {
• The function is not tail-recursive because if (n==0) return a;
the value returned by fact(n-1) is used in return fac(n-1, n*a);
fact(n) and call to fact(n-1) is not the last }
thing done by fact(n). • what is use of 'a'?
• Can we convert a recursive function to a - 'a' (accumlator) would be an
tail-recursive function?
extra parameter used for the purpose
• Can be done using a jacket function for
of storing the partial results.
every recursive call/function.
Recursive to Tail-Recursive Function Cont..
int factorial (int n) { Let us calculate 5!
return fac (n,1) } return fac (5,1)
fac(5,1) = return fac(4, 5); a=5
int fac(int n, int a) { fac(4,5) = return fac (3, 20); a=20
if (n==0) return a; fac(3,20)= return fac (2,60); a=60
return fac(n-1, n*a); } fac(2,60) = return fac(1, 120) ; a=120
fac(1,120) = return fac(0, 120) ; a=120
fac(0, 120) = return a, i.e.,120
• The general case of the transformation employs conversion to what is
known as continuation-passing style.
• In effect, a recursive function can always avoid doing any work after
returning from a recursive call by passing that work into the recursive call,
in the form of a continuation.
Approach-I: Using Tree Recursion
int fib (int n) Ex. fib(100)
fib(5) { How many times
fib (95) may have to
if (n==0)
be calculated?
return 0;
fib(4) fib(3)
else if (n==1)
return 1; Complexity?
fib(3) fib(2) fib(2) fib(1)
else -Exponential
return (fib(n-1),
fib fib
fib(2)
(1)
fib(1)
(0)
fib(1) fib(0) fib(n-2)) Iterative version -
o(n) (linear)
}
fib
fib(1)
(0)
Tree recursion-one fun call leading to two recursive calls
Approach-II:Memoization
• Instead of repeatedly computing the same fib(5)
thing, we can store them in an auxillary
memory.
fib(5) = fib(4) + fib(3)
int fib_values[200]= {-1};
int fib(int n){
if (fib_values[n]!=-1) return (fib_values[n]); fib(4) = fib(3) + fib(2)
else if (n=0) { fib_values[0] = 0; return 0;}
else if (n==1) { fib_values[1]=1; return 1;}
else { fib_values[n] = fib(n-1) + fib(n-2); fib(3) = fib(2) + fib(1)
return (fib_values[n]);}
}
fib(2) = fib(1) + fib (0)
Approach-II:Memoization
• An optimization technique used primarily to speed up computer
programs by storing the results of expensive function calls and
returning the cached result when the same inputs occur again.
• Not a clean code.
• Array is used as a global array.
• We are trading space with time here.
• Trying to decrease the time, but space is increased.
Approach-III:Using Static
• int fib(int n) • We can use static array
{ inside the function instead
static int fib_values[n]; of a global array.
// fib_values is stored in data
segment in the memory • Values persist across the
function calls.
// rest is same code.
}
Using Tail Recursive version of Fibo. Series
5
• int fibonacci (int n) fib(1,3,5) • No space required
{ for array
return fib(n, 0, 1} fib(2,2,3)
} • No extra space for
fib(3,1,2) an activation record
int fib(int n, int t1, int t2)
{ fib(4,1,1) •Same complexity as
if (n==0) return t1; that of iterative
fib(5,0,1) version of fib series
else if (n==1) return t2;
else return (fib(n-1, t2, t1+t2)); fibonacci(5)
}
Compiler's role for Tail recursive function
• Smart compilers written for functional languages make
these transformations of recursive to tail-recursive of
their own.
• General Steps
– Try to make the program tail recursive
– If not possible, try to make use of Memoization
– If not, then use recursion
Stack Smashing/ Buffer Overflow
#include <stdlib.h> main()
#include <stdio.h>
{
#include <string.h>
int get_accnt_num(FILE *s) FILE *fp;
{ int r;
char buf[100]; fp = fopen("xyz.txt", "r");
char *p = buf; r = get_accnt_num(fp);
do{
printf("The no. of bytes read is
*p = getc(s);
}while(*p++!='\n'); %d\n", r);
*p = '\0'; }
return (atoi(buf));
}
Stack Smashing/ Buffer Overflow
• If a process is trying to access/write memory beyond the
storage space allocated for the function's local variables
(which does not belong to your process) , then the stack
smashing or stack buffer overflow is said to have occured.
• If the file xyz.txt contains more than 100 characters, then this
problem will occur in C/C++ as these languages do not check
array bounds in order to speed up the program but are
insecure.
• The language implementation must do this checking at run
time.
Stack Smashing Cont..
• File with characters>100, an
array will overflow, buffer will
overwrite p.
buf (Size =100)
• If this is done further, then a
Saved registers
clever programmer can replace
Saved FP
return address with his/her own
return address address to get the control of the
(Supposed to system.
contain the address
of a caller)
A typical stack frame
References
• Programming Language Pragmatics by Michael L. Scott,
3rd Edition (Elsevier)
