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