Transcript Recursion

Recursion
by
Ender Ozcan
Recursion in computing


Recursion in computer programming
defines a function in terms of itself.
Advantage: Infinite set of possible
sentences, designs or other data can be
defined, parsed or produced by a finite
computer program.
Example: the natural numbers


The canonical example of a recursively defined set is
given by the natural numbers:
 0 is in N
 if n is in N, then n + 1 is in N
 The set of natural numbers is the smallest set
satisfying the previous two properties.
Here's an alternative recursive definition of N:
 0, 1 are in N;
 if n and n + 1 are in N, then n + 2 is in N;
 N is the smallest set satisfying the previous two
properties.
Example: Factorial
integer Fact ( integer X ) {
if X < 0 then return -1; // invalid arg
if X = 1 then return 1;
return Fact(X-1) * X;
}


Computing 4!, requires a call to Fact(4)
Fact(4)  returns Fact(3)*4
6*4=24
 Fact(3)  returns Fact(2)*3
2*3=6
 Fact(2) returns Fact(1)*2
1*2=2
 Fact(1)  returns 1
Basic steps of recursive programs






Initialize the algorithm.
Termination Criteria – check to see whether the
current value(s) being processed match the base case.
If so, process and return the value.
Redefine the answer in terms of a smaller or simpler
sub-problem or sub-problems.
Run the algorithm on the sub-problem.
Combine the results in the formulation of the answer.
Return the results.
Example – Sum of n numbers

Suppose we have a list of n numbers, and we
want to sum them.
1. Initialize the algorithm. This algorithm's seed value is the first
number to process and is passed as a parameter to the function.
2. Check for the base case. The program needs to check and see if
the list is empty. If so, we return zero because the sum of all
members of an empty list is zero.
3. Redefine the answer in terms of a simpler sub-problem. We can
define the answer as the sum of the rest of the list plus the
contents of the current number. To determine the sum of the rest
of the list, we call this function again with the next number.
4. Combine the results. After the recursive call completes, we add
the value of the current node to the results of the recursive call.
Linked List
data
Linked list is a basic data structure,
used to hold a sequence of items in
memory
<3, 159, 78>
next
3
data
next
159
data
head
tail
next
78
C implementation using linked lists
int sum_list(struct list_node *l)
{
if(l == NULL) return 0;
return l.data + sum_list(l.next);
}
Comparing loops with recursive functions
Properties Loops
Recursive
functions
Repetition
Execute the same block of code
repeatedly to obtain the result;
signal their intent to repeat by
either finishing the block of code
or issuing a continue command.
Execute the same block
of code repeatedly to
obtain the result; signal
their intent to repeat by
repeat by calling
themselves.
Terminating
conditions
In order to guarantee that it will
terminate, a loop must have one
or more conditions that cause it
to terminate and it must be
guaranteed at some point to hit
one of these conditions.
In order to guarantee that
it will terminate, a
recursive function
requires a base case that
causes the function to
stop recursing.
State
Current state is updated as the
loop progresses.
Current state is passed as
parameters.
To Loop or Not To Loop
Rule of thumb for programmers

If you can solve a problem using
iteration, avoid recursion
Fibonacci Sequence


<0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377,
610, 987, …>
The original problem that
Fibonacci investigated (in
the year 1202) was about
how fast rabbits could
breed in ideal
circumstances (assuming
they don’t die).
nth Fibonacci Number


fib(n) = fib(n – 1) + fib (n – 2) for n>1, and
fib(0)=0, fib(1)=1.
C program computing nth fibonacci
number:
int fib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}
nth Fibonacci Number-Revisited
fib(5)
fib(4)
fib(3)
fib(1)
fib(2)
fib(1)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
fib(0)
fib(2)
fib(1)
fib(0)
Try to avoid solving overlapping
sub-problem instances
Recursive vs. Iterative Solution
int fib(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return
fib(n-1) + fib(n-2);
}
int fib(int n)
{
int i, *fib=new int[n];
fib[0]=0;
fib[1]=1;
for (i=2; i<n; i++)
fib[i]=fib[i-1]+fib[i-2];
return fib[n];
}
Running time is ~ a(n+n)
Running time is ~ cn
Tower of Hanoi Puzzle


Puzzle was invented by the French
mathematician Edouard Lucas in 1883.
We are given a tower of 8 disks, initially
stacked in increasing size on one of three pegs.
The objective is to transfer the entire tower to
one of the other pegs, moving only one disk at
a time and never a larger one onto a smaller.
Recursive Solution

Call the three pegs Src (Source), Aux
(Auxiliary) and Dst (Destination).
Src
Aux
n disks
Dst
Recursive Solution – Step 1

Move the top n-1 disks from Src to Aux (using
Dst as an intermediary peg)
Src
Aux
Dst
n-1 disks
Recursive Solution – Step 2

Move the bottom disks from Src to Dst
Src
Aux
Dst
Recursive Solution – Step 3

Move n-1 disks from Aux to Dst (using Src as
an intermediary peg)
Src
Aux
Dst
Pseudocode

Solve(n, Src, Aux, Dst)




if n is 0 return
Solve(n-1, Src, Dst, Aux)
Move from Src to Dst
Solve(n-1, Aux, Src, Dst)
Analysis of the Algorithm I

Assume than T(n) is the number of steps
required to move n disks from Src to Dst
Src
Aux
n disks
Dst
Analysis of the Algorithm II

Moving the top n-1 disks from Src to Aux will
take T(n-1) steps
Src
Aux
Dst
n-1 disks
Analysis of the Algorithm III

Moving the bottom disk from Src to Dst will
take a single step
Src
Aux
Dst
Analysis of the Algorithm IV

Moving n-1 disks from Aux to Dst will take
T(n-1) steps
Src
Aux
Dst
Overall Complexity

T(n) = 2T(n-1) + 1 {T(n-1) = 2T(n-2) + 1 }






T(n) = 22T(n-2) + 2 + 1
substitute T(n-1)
T(n) = 23T(n-3)+ 22 + 2 + 1
…
T(n) = 2n-1 T( n-(n-1)) +…+ 23 +22+2+1
T(1)=1
T(n) = 2n-1 +…+ 23 +22+2+1 (geometric series)
T(n) = 2n - 1