Transcript Recursion Review - Department of Computer Science

A Review of Recursion
Dr. Jicheng Fu
Department of Computer Science
University of Central Oklahoma
Objectives (Chapter 5)






Definition of recursion and how it works
Recursion tree
Divide and Conquer
Designing Recursive Algorithm
Tail Recursion
When Not to Use Recursion
Definition

Recursion is the case when a function
invokes itself or invokes a sequence of other
functions, one of which eventually invokes
the first function again

Suppose we have 4 functions: A, B, C and D


Recursion: A → B → C → D → A
Recursion is a feature of some programming
languages, such as C++ and Java

No recursion feature in Cobol and Fortran
Tree of Subprogram Calls
M() {
A();
D(2);
}
A() {
B();
C();
}
B() {}
C() {
D(0);
}
D(int n) {
if (n>0) D(n-1);
}
Recursion Tree


A recursion tree is a tree of subprogram calls that
show recursive function calls
Note that the tree shows the calls of functions



A function called from only one place, but within a loop
executed more than once, will appear several times in the
tree
If a function is called from a conditional statement that is
not executed, then the call will not appear in the tree
The total number of function calls is proportional to
the total number of nodes of the recursion tree
Why Recursion

Divide and conquer


To obtain the answer to a large problem, the large
problem is often reduced to one or more problems
of a similar nature but a smaller size
Subproblems are further divided until the size of
the subproblems is reduced to some smallest,
base case, where the solution is given directly
without further recursion
A Mathematics Example

The factorial function

Informal definition:

Formal definition:

Problem: 4!
4! = 4 * 3!
= 4 * (3 * 2!)
= 4 * (3 * (2 * 1!))
= 4 * (3 * (2 * (1 * 0!)))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
=4*6
= 24

Every recursive process consists of two parts:



Do not try to understand a recursive algorithm by
working the general case all the way down to the
stopping rule


A smallest, base case that is processed without recursion;
A general method that reduces a particular case to one or
more of the smaller cases, thereby eventually reducing the
problem all the way to the base case.
It may be helpful to work a small example
Instead, only think about the correctness of the base
bases and the recursive cases

If they are correct, then the recursive algorithm should be
correct

Example: Factorial
int factorial (int n)
/* Pre: n is an integer no less than 0
Post: The factorial of n (n!) is returned
Uses: The function factorial recursively */
{
if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
}

Example: Inorder traversal of a binary tree
template <class Entry>
void Binary_tree<Entry> ::
recursive_inorder(Binary_node<Entry> *sub_root,
void (*visit)(Entry &))
/* Pre: sub_root is either NULL or points to a subtree of the
Binary_tree
Post: The subtree has been traversed in inorder sequence
Uses: The function recursive_inorder recursively */
{
if (sub_root != NULL) {
recursive_inorder(sub_root->left, visit);
(*visit)(sub_root->data);
recursive_inorder(sub_root->right, visit);
}
}

The Hanoi Tower

A good example of solving a big problem using
the divide and conquer and recursion technology

Pp. 163-168
Designing Recursive Algorithm

Find the key step



Begin by asking yourself, “How can this problem
be divided into parts?”
Once you have a simple, small step toward the
solution, ask whether the remainder of the
problem can be solved in the same or a similar
way
Find a stopping rule (base case)

The stopping rule is usually the small, special
case that is trivial or easy to handle without
recursion

Outline your algorithm


Combine the stopping rule and the key step, using
an if statement to select between them
Check termination

Verify that the recursion will always terminate


All possible base cases are considered
Be sure that your algorithm correctly handles all
possible base cases

Exercise

Write a recursive function for the following
problem:
Given a number n (n > 0), if n is even, calculate 0
+ 2 + 4 + ... + n. If n is odd, calculate 1 + 3 + 5
+ ... + n

About a recursion tree


The height of the tree is closely related to the
amount of memory that the program will require
The total size of the tree reflects the number of
times the key step will be done
Tail Recursion

Definition


Problem


Tail recursion occurs when the last-executed statement of
a function is a recursive call to itself
Since the recursive call is the last action of the function,
there is no need for recursion
No difference in execution time for most compilers


Compiler will transform it into a loop
Functional programming often requires the transformation
of a non-tail recursion into a tail recursion so that
optimizations can be done
int sumto(int n){
if (n <= 0) return 0;
else return sumto(n-1) + n;
}
int sumto1(int n, int sum){
if (n <= 0) return sum;
else return sumto1(n-1,sum+n);
}
Guidelines and Conclusions of Recursion

When not to use recursion


Use the recursion tree to analyze
If a function call makes only one recursive call to
itself, then its recursion tree is a chain



In such a case, transformation from recursion to iteration
is often easy and can save both space and time
If the recursion tree involves duplicate tasks,
some data structure other than stack may be
appropriate
Read pp. 176-180
Example: Fibonacci Numbers

Fibonacci numbers are defined by the recurrence
relation

Recursive solution
int fibonacci(int n)
/* fibonacci : recursive version */
{
if (n <= 0) return 0;
else if (n == 1) return 1;
else return fibonacci(n − 1) + fibonacci(n − 2);
}

Problems


The results stored on the stack are discarded
There are lots of duplicate tasks in the tree

Non-recursive solution
int fibonacci(int n)
/* fibonacci : iterative version */
{
int last_but_one; // second previous Fibonacci number, Fi−2
int last_value; // previous Fibonacci number, Fi−1
int current; // current Fibonacci number Fi
if (n <= 0) return 0;
else if (n == 1) return 1;
else {
last_but_one = 0;
last value = 1;
for (int i = 2; i <= n; i++) {
current = last_but_one + last_value;
last_but_one = last_value;
last_value = current;
}
return current;
}
}


Recursion can always be replaced by
iteration and stacks
Conversely, any iterative program that
manipulates a stack can be replaced by a
recursive program without a stack
Analyzing Recursive Algorithms

Often a recurrence equation is used as the starting
point to analyze a recursive algorithm


In the recurrence equation, T(n) denotes the running time
of the recursive algorithm for an input of size n
We will try to convert the recurrence equation into a
closed form equation to have a better understanding
of the time complexity


Closed Form: No reference to T(n) on the right side of the
equation
Conversions to the closed form solution can be very
challenging

Example: Factorial
int factorial (int n)
/* Pre: n is an integer no less than 0
Post: The factorial of n (n!) is returned
Uses: The function factorial recursively */
{
if (n == 0)
return 1;
else
return n * factorial (n - 1);
}
}
1
1
T (n  1)  3

The time complexity of factorial(n) is:
if n  0
2
T (n)  
T (n  1)  4 if n  0

T(n) is an arithmetic sequence with the common difference
4 of successive members and T(0) equals 2
T (n )  T (0)  nd  2  4n

3+1: The
comparison
is included
The time complexity of factorial is O(n)

Fibonacci numbers
int fibonacci(int n)
/* fibonacci : recursive version */
{
if (n <= 0) return 0;
else if (n == 1) return 1;
else return fibonacci(n − 1) + fibonacci(n − 2);
}

The time complexity of fibonacci is:
2

T (n)   3
T (n  1)  T (n  2)  6



if n  0
if n  1
if n  1
Theorem (in Section A.4): If F(n) is defined by a Fibonacci
sequence, then F(n) is (gn), where g  (1  5 ) / 2
The time complexity is exponential: O(gn)