Transcript Recursion

ICS220 – Data Structures and
Algorithms
Dr. Ken Cosh
Week 5
Review
• Stacks
– LIFO
• Queues
– FIFO
• Priority Queues
This weeks Topic
• Recursion
– Tail Recursion
– Non-tail Recursion
– Indirect Recursion
– Nested Recursion
– Excessive Recursion
Defining new things
• A basic rule for designing new things, is
only to include terms which have already
been defined.
– One wouldn’t say “Mix 3 flugglepips with a
hippyfrick”
• To define an object in terms of itself is a
serious violation of this rule – a vicious
circle.
• However, definitions such as this are called
recursive definitions.
Infinite Sets
• When defining an infinite set, a complete
list of the set is impossible, so recursion is
often used to define them.
• With large finite sets, it can be more
efficient to also define them using
recursion.
Consider defining Natural Numbers
0∈
if n ∈
then (n+1) ∈
there are no other objects in set
According to these rules, the set of natural
numbers contains;
0, 0+1, 0+1+1… etc.
Recursion vs Formula
• When using a recursive definition, it is necessary
to calculate every value;
– for instance to calculate 6!, first we need to know 5!,
and then 4! etc.
• Therefore, sometimes being able to use a
formula can be less computationally demanding.
– If n=0, g(n) = 1
– if n>0, g(n) = 2*g(n-1)
• This is a recursive function, which can be
converted to a simple formula – What is it?
Function Calls
• What happens when a function is called?
– If there are formal parameters, they are initialised to
the values passed.
– The return address – for where the program needs to
resume after the function completes needs to be
stored.
• This return address is key, and for efficiency, the
memory for the address is allocated dynamically
– using the runtime stack.
• The runtime stack contains an activation record
(or frame) for each calling function.
Activation Records
• Activation Records contain;
– Values for all parameters to the function (either
addresses for call by reference, or copies for call by
value)
– Local variables can be stored elsewhere, but the
activation record will store pointers to their locations.
– The return address, where to resume control in the
calling function – the address of the next instruction in
the calling function
– A dynamic link, or pointer, to the caller’s activation
record.
– The returned value for a non-void function.
Runtime stack
Parameters and Local Variables
Activation Record
for f3()
Dynamic Link
Return Address
Return Value
Parameters and Local Variables
Activation Record
for f2()
Dynamic Link
Return Address
Return Value
Parameters and Local Variables
Activation Record
for f1()
Activation Record
for main()
Dynamic Link
Return Address
Return Value
Recursion
• An activation record is created whenever a
function is called.
• This means that each recursive call is not
really a function calling itself, but instead,
an instance of a function calling another
instance of a function.
!Factorial!
• Consider the factorial problem;
int fact(int n)
{
if (n==0)
return 1;
else return n* fact(n-1);
}
• What happens when this function is called?
answer = fact(6)
Tail Recursion
• Tail recursion occurs when the final
instruction in a function is the recursive
call (and there have been no prior
recursive calls).
• An example is the factorial function on the
previous slide.
Non-Tail Recursion
• Conversely, in nontail recursion, the recursive call is not
the final instruction in the function. Consider this
function.
void reverse() {
char ch;
cin.get(ch);
if (ch != ‘\n’) {
reverse();
cout.put(ch);
}
}
Indirect Recursion
• Direct recursion occurs when a function directly
calls itself; indirect recursion is when a function
calls a function which calls itself – or similar.
– f() -> g() -> f()
• Consider a buffer, which receives data, decodes
it and stores it. This has 3 functions;
– receive(), decode(), store()
• While there is data to be received, they will
repeatedly call each other.
Nested Recursion
• Nested recursion occurs when a function is not
only defined in terms of itself, but is also a
parameter to the function.
If n=0,
If n>0, m=0
Else
A(n,m) = m+1
A(n,m) = A(n-1,1)
A(n-1, A(n,m-1))
• N.B. this function (known as the Ackermann
function) grows very fast
– A(4,1) is 265536-3,
• The recursive definition is simple, but as it grows
faster than addition, multiplication of
exponentiation, defining it arithmetically is not
practical.
Why Recurse?
• Logical Simplicity
– Some mathematical formulas are naturally
recursive – an arithmetic / iterative solution
may not be simple.
• Readability
– Recursive functions are often easier to
understand and work through.
Why not recurse?
• Excessive use of the runtime stack
– With the data being stored on the runtime
stack, there is danger of it running out of
space.
• Speed
– Some recursive functions can be slow and
inefficient.
Fibonacci
Int Fib(int n)
{
if (n<2)
return n;
else
return Fib(n-2) + Fib(n-1);
}
How efficient is this recursive function?
Fib(5)
• To calculate Fib(5), first we need Fib(4)
and Fib(3).
– To calculate Fib(4), we need Fib(3) and
Fib(2).
• To calculate Fib(3), we need Fib(2) and Fib(1).
– To calculate Fib(2), we need Fib(1) and Fib(0).
• To calculate Fib(2), we need Fib(1) and Fib(0).
– To calculate Fib(3), we need Fib(2) and
Fib(1).
• To calculate Fib(2), we need Fib(1) and Fib(0).
Repetition
• Notice that on the previous slide (which
isn’t complete), we make calls to calculate
Fib(2) 3 times. Each time the call is made
the value is forgotten by the PC, because
of the way unstacked data is thrown away.
• To calculate Fib(6), there are 25 calls to
the Fib function, and 12 addition
operations.
Fib(6)
Fib(4)
Fib(2)
Fib(0)
Fib(1)
Fib(5)
Fib(3)
Fib(1)
Fib(3)
Fib(2)
Fib(0)
Fib(1)
Fib(2)
Fib(4)
Fib(2)
Fib(3)
Fib(1) Fib(0) Fib(1) Fib(0) Fib(1) Fib(1) Fib(2)
Fib(0) Fib(1)
Fib Growth
• The number of additions required for a
recursive definition is;
– Fib(n + 1) - 1
• For each addition required, there are 2
function calls;
– 2*Fib(n + 1) - 1
Fib Growth
n
Fib(n+1)
Number of
Additions
Number of
Calls
6
13
12
25
10
89
88
177
15
987
986
1,973
20
10,946
10,945
21,891
25
121,393
121,392
242,785
30
1,346,269
1,346,268
2,692,537
Recursive Fib
• The recursive Fib algorithm is simple. But
the number of calls, and run time grows
exponentially with n.
– Recursive Fib is only really practical with
small n.
Alternative Fib
int iterativeFib(int n)
{
int previous = -1, result=1;
for(int i=0; i<=n; ++i)
{
int const sum=result+previous;
previous = result;
result = sum;
}
return result;
}
Iterative Fib
• The iterative version of fib, is clearly more
efficient.
• There is however an even more efficient,
mathematical approach to approximating Fib(n);
int deMoivreFib(int n) {
return ceil(exp(n*log(1.6180339897)log(2.2360679775))-.5);
}