Data Structures Using C++ 2E
Chapter 6
Recursion
Edited by Malak Abdullah
Jordan University of Science and Technology
Objectives
• Learn about recursive definitions
• Explore the base case and the general case of a
recursive definition
• Learn about recursive algorithm
• Learn about recursive functions
• Explore how to use recursive functions to
implement recursive
Data Structures Using C++ 2E Edited by Malak Abdullah 2
Jordan University of Science and Technology
Recursive Definitions
• Recursion
– Process of solving a problem by reducing it to smaller
versions of itself • 5!
• Example: factorial problem • 5 * 4!
– 5! • 5 * 4 * 3!
• 5 x 4 x 3 x 2 x 1 =120 • 5 * 4 * 3 * 2!
– If n is a nonnegative • 5 * 4 * 3 * 2 * 1 = 120
• Factorial of n (n!) defined as follows:
Data Structures Using C++ 2E Edited by Malak Abdullah 3
Jordan University of Science and Technology
Recursive Definitions (cont’d.)
• Direct solution (Equation 6-1)
– Right side of the equation contains no factorial
notation
• Recursive definition
– A definition in which something is defined in terms of
a smaller version of itself
• Base case (Equation 6-1)
– Case for which the solution is obtained directly
• General case/ Recursive case (Equation 6-2)
– Case for which the solution is obtained indirectly
using recursion
Data Structures Using C++ 2E Edited by Malak Abdullah 4
Jordan University of Science and Technology
Recursive Definitions (cont’d.)
• Recursion insight gained from factorial problem
– Every recursive definition must have one (or more)
base cases
– General case must eventually reduce to a base case
– Base case stops recursion
• Recursive algorithm
– Finds problem solution by reducing problem to
smaller versions of itself
• Recursive function
– Function that calls itself
Data Structures Using C++ 2E Edited by Malak Abdullah 5
Jordan University of Science and Technology
Fun1(3)
Print 3
Call fun2(2) ...
Print *
Fun2(2)
Print 2
Call fun3(1) ...
Print &
Fun3(1)
Print 1
Print $
Edited by Malak Abdullah
Jordan University of Science and Technology
Fun(3)
Print 3
Call fun(2) ...
Print a= 3
Fun(2)
Print 2
Call fun(1) ...
Print a= 2
Fun(1)
Print 1
Call fun(0) ...
Print a= 1
Fun(0)
Edited by Malak Abdullah
Jordan University of Science and Technology Print a= 0
5!= 5 * ( 4 *( 3* (2 * (1))))
Fact1(5)
void main( )
{ 5 * Fact1(4)
cout<< fact (5)<<endl;
4 * Fact1(3)
}
3 * Fact1(2)
2 * Fact1(1)
1 * Fact1(0)
Edited by Malak Abdullah
Jordan University of Science and Technology
5!= 5 * ( 4 *( 3* (2 * (1))))
Fact1(5)
120
void main( )
{ 5 * Fact1(4)
24
cout<< fact (5)<<endl;
4 * Fact1(3)
6
}
3 * 2
Fact1(2)
2 * Fact1(1)
1
1 * Fact1(0)
1
Edited by Malak Abdullah
Jordan University of Science and Technology
Print the number in reverse →1357 7531
Reverse(1357)
Print 1357 % 10 →7
Call reverse(135)
Reverse(135)
Print 135 % 10 →5
Call reverse(13)
Reverse(13)
Print 13 % 10 →3
Call reverse(1)
Reverse(1)
Print 1
Edited by Malak Abdullah
Jordan University of Science and Technology
Recursive Definitions (cont’d.)
• Recursive function implementing the factorial
function
FIGURE 6-1 Execution of fact(4)
Data Structures Using C++ 2E Edited by Malak Abdullah 11
Jordan University of Science and Technology
Recursive Definitions (cont’d.)
• Recursive function notable comments
– Recursive function has unlimited number of copies of itself
(logically)
– Every call to a recursive function has its own
• Code, set of parameters, local variables
– After completing a particular recursive call
• Control goes back to calling environment (previous call)
• Current (recursive) call must execute completely before control
goes back to the previous call
• Execution in previous call begins from point immediately
following the recursive call
Data Structures Using C++ 2E Edited by Malak Abdullah 12
Jordan University of Science and Technology
Recursive Definitions (cont’d.)
• Direct and indirect recursion
– Directly recursive function
• Calls itself
– Indirectly recursive function
• Calls another function, eventually results in original function call
• Requires same analysis as direct recursion
• Base cases must be identified, appropriate solutions to them
provided
• Tracing can be tedious
– Tail recursive function
• Last statement executed: the recursive call
Data Structures Using C++ 2E Edited by Malak Abdullah 13
Jordan University of Science and Technology
5!= 5 * ( 4 *( 3* (2 * (1))))
Fact1(5)
5 Fact1(4)
4 Fact1(3)
3 Fact1(2)
2 Fact1(1)
1 Fact1(0)
Edited by Malak Abdullah
Jordan University of Science and Technology
5!= ((((1) * 2) * 3) * 4) * 5
Fact2(5)
5 Fact2(4)
4 Fact2(3)
3 Fact2(2)
2 Fact2(1)
1 Fact2(0)
Edited by Malak Abdullah
Jordan University of Science and Technology
Indirectly Recursive Infinite Recursion
Edited by Malak Abdullah
Jordan University of Science and Technology
Recursive Definitions (cont’d.)
• Infinite recursion
– Occurs if every recursive call results in another
recursive call
– Executes forever (in theory)
– Call requirements for recursive functions
• System memory for local variables and formal
parameters
• Saving information for transfer back to right caller
– Finite system memory leads to
• Execution until system runs out of memory
• Abnormal termination of infinite recursive function
Data Structures Using C++ 2E Edited by Malak Abdullah 17
Jordan University of Science and Technology
Recursive Definitions (cont’d.)
• Requirements to design a recursive function
– Understand problem requirements
– Determine limiting conditions
– Identify base cases, providing direct solution to each
base case
– Identify general cases, providing solution to each
general case in terms of smaller versions of itself
Data Structures Using C++ 2E Edited by Malak Abdullah 18
Jordan University of Science and Technology
Fibonacci Number
• Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34 . . .
• Given first two numbers (a1 and a2)
– nth number an, n >= 3, of sequence given by: an = an-
1 + an-2
• Recursive function: rFibNum
– Determines desired Fibonacci number
– Parameters: three numbers representing first two
numbers of the Fibonacci sequence and a number n,
the desired nth Fibonacci number
– Returns the nth Fibonacci number in the sequence
Data Structures Using C++ 2E Edited by Malak Abdullah 19
Jordan University of Science and Technology
Fibonacci Number (cont’d.)
• Third Fibonacci number
– Sum of first two Fibonacci numbers
• Fourth Fibonacci number in a sequence
– Sum of second and third Fibonacci numbers
• Calculating fourth Fibonacci number
– Add second Fibonacci number and third Fibonacci
number
Data Structures Using C++ 2E Edited by Malak Abdullah 20
Jordan University of Science and Technology
If x= 1 then Fib(x)= 1
If x= 2 then Fib(x)=2
Otherwise Fib(x)= Fib(x-1) + Fib(x-2)
• Fib(3)= Fib(2) + Fib(1) = 3
• Fib(4)= Fib(3) + Fib(2) = 5
• Fib(5)= Fib(4) + Fib(3) = 8
• And so on...
• Fib(10) = . . .
Edited by Malak Abdullah
Jordan University of Science and Technology
Fibonacci Number (cont’d.)
• Recursive algorithm
– Calculates nth Fibonacci number
• a denotes first Fibonacci number
• b denotes second Fibonacci number
• n denotes nth Fibonacci number
Data Structures Using C++ 2E Edited by Malak Abdullah 22
Jordan University of Science and Technology
Fibonacci Number (cont’d.)
• Recursive function implementing algorithm
• Trace code execution
• Review code on page 368 illustrating the function
rFibNum
Data Structures Using C++ 2E Edited by Malak Abdullah 23
Jordan University of Science and Technology
Fibonacci(1)= 2 , Fibonacci(2)= 3
Fibonacci(5)=????
rFibNum(2,3,5) 13
8 5
rFibNum(2,3,4) + rFibNum(2,3,3)
5
rFibNum(2,3,3) + rFibNum(2,3,2) rFibNum(2,3,2) + rFibNum(2,3,1)
rFibNum(2,3,2) + rFibNum(2,3,1) 3 3 2
3 2 Edited by Malak Abdullah
Jordan University of Science and Technology
Another example
Fib(4)
Fib(3) Fib(2)
Fib(2) Fib(1) Fib(1) Fib(0)
Fib(1) Fib(0) 1 1 0
1 0
Edited by Malak Abdullah
Jordan University of Science and Technology
Fibonacci Number (cont’d.)
FIGURE 6-7 Execution of rFibNum(2, 3, 4)
Data Structures Using C++ 2E Edited by Malak Abdullah 26
Jordan University of Science and Technology
Largest Element in an Array
FIGURE 6-2 list with six elements
• list: array name containing elements
• list[a]...list[b] stands for the array
elements list[a], list[a + 1], ...,
list[b]
• list length =1
– One element (largest)
• list length >1
maximum(list[a],
largest(list[a + 1]...list[b]))
Data Structures Using C++ 2E Edited by Malak Abdullah 27
Jordan University of Science and Technology
5 3 6 2 4
5 3 6 2 4
3 6 2 4
6 2 4
2 4
Edited by Malak Abdullah
Jordan University of Science and Technology
5 3 6 2 4
5 3 6 2 4
3 6 2 4
6 4
Edited by Malak Abdullah
Jordan University of Science and Technology
5 3 6 2 4
5 3 6 2 4
3 6
Edited by Malak Abdullah
Jordan University of Science and Technology
5 3 6 2 4
5 6
Edited by Malak Abdullah
Jordan University of Science and Technology
Max is 6
Edited by Malak Abdullah
Jordan University of Science and Technology
Largest(arr, 0, 3)
3 ,6, 2, 5
Max = 6
3 > Max ???
Largest(arr, 1, 3)
6 , 2, 5
Max = 5
6 > Max ???
0 1 2 3 Largest(arr, 2, 3)
3 6 2 5 2, 5
Max = 5
2 > Max ???
Largest(arr, 3, 3)
5
Edited by Malak Abdullah
Jordan University of Science and Technology
Largest Element in an Array (cont’d.)
• maximum(list[0],
largest(list[1]...list[5]))
• maximum(list[1],
largest(list[2]...list[5]), etc.
• Every time previous formula used to find largest
element in a sublist
– Length of sublist in next call reduced by one
Data Structures Using C++ 2E Edited by Malak Abdullah 34
Jordan University of Science and Technology
Largest Element in an Array (cont’d.)
• Recursive algorithm in pseudocode
Data Structures Using C++ 2E Edited by Malak Abdullah 35
Jordan University of Science and Technology
Largest Element in an Array (cont’d.)
• Recursive algorithm as a C++ function
Data Structures Using C++ 2E Edited by Malak Abdullah 36
Jordan University of Science and Technology
Largest Element in an Array (cont’d.)
FIGURE 6-3 list with four elements
• Trace execution of the following statement
cout << largest(list, 0, 3) << endl;
• Review C++ program on page 362
– Determines largest element in a list
Data Structures Using C++ 2E Edited by Malak Abdullah 37
Jordan University of Science and Technology
Largest Element in an Array (cont’d.)
FIGURE 6-4 Execution of largest(list, 0, 3)
Data Structures Using C++ 2E Edited by Malak Abdullah 38
Jordan University of Science and Technology
Print a Linked List in Reverse Order
• Function reversePrint
– Given list pointer, prints list elements in reverse order
• Figure 6-5 example
– Links in one direction
– Cannot traverse backward starting from last node
FIGURE 6-5 Linked list
Data Structures Using C++ 2E Edited by Malak Abdullah 39
Jordan University of Science and Technology
Print a Linked List in Reverse Order
(cont’d.)
• Cannot print first node info until remainder of list
printed
• Cannot print second node info until tail of second
node printed, etc.
• Every time tail of a node considered
– List size reduced by one
– Eventually list size reduced to zero
– Recursion stops
Data Structures Using C++ 2E Edited by Malak Abdullah 40
Jordan University of Science and Technology
Print a Linked List in Reverse Order
(cont’d.)
• Recursive algorithm in pseudocode
• Recursive algorithm in C++
Data Structures Using C++ 2E Edited by Malak Abdullah 41
Jordan University of Science and Technology
reversePrint(nodeType * current ) Current → 4
{
if(current != NULL)
{
reversePrint(current→link) Current → 8
cout<< current →info;
}
}
Current → 9
NULL
4 8 9
stackTop
current current current current
9 8 4
Edited by Malak Abdullah
Jordan University of Science and Technology
Print a Linked List in Reverse Order
(cont’d.)
• Function template to implement previous algorithm
and then apply it to a list
Data Structures Using C++ 2E Edited by Malak Abdullah 43
Jordan University of Science and Technology
Print a Linked List in Reverse Order
(cont’d.)
FIGURE 6-6 Execution of the statement reversePrint(first);
Data Structures Using C++ 2E Edited by Malak Abdullah 44
Jordan University of Science and Technology
Print a Linked List in Reverse Order
(cont’d.)
• The function printListReverse
– Prints an ordered linked list contained in an object of
the type linkedListType
Data Structures Using C++ 2E Edited by Malak Abdullah 45
Jordan University of Science and Technology
Tower of Hanoi
• Object
– Move 64 disks from first needle to third needle
• Rules
– Only one disk can be moved at a time
– Removed disk must be placed on one of the needles
– A larger disk cannot be placed on top of a smaller disk
FIGURE 6-8 Tower of Hanoi problem with three disks
Data Structures Using C++ 2E Edited by Malak Abdullah 46
Jordan University of Science and Technology
Tower of Hanoi (cont’d.)
• Case: first needle contains only one disk
– Move disk directly from needle 1 to needle 3
• Case: first needle contains only two disks
– Move first disk from needle 1 to needle 2
– Move second disk from needle 1 to needle 3
– Move first disk from needle 2 to needle 3
• Case: first needle contains three disks
Data Structures Using C++ 2E Edited by Malak Abdullah 47
Jordan University of Science and Technology
Tower of Hanoi (cont’d.)
FIGURE 6-9 Solution to Tower of Hanoi problem with three disks
Data Structures Using C++ 2E Edited by Malak Abdullah 48
Jordan University of Science and Technology
Tower of Hanoi (cont’d.)
• Generalize problem to the case of 64 disks
– Recursive algorithm in pseudocode
Data Structures Using C++ 2E Edited by Malak Abdullah 49
Jordan University of Science and Technology
Tower of Hanoi (cont’d.)
• Generalize problem to the case of 64 disks
– Recursive algorithm in C++
Data Structures Using C++ 2E Edited by Malak Abdullah 50
Jordan University of Science and Technology
Tower of Hanoi (cont’d.)
• Analysis of Tower of Hanoi
– Time necessary to move all 64 disks from needle 1
to needle 3
– Manually: roughly 5 x 1011 years
• Universe is about 15 billion years old (1.5 x 1010)
– Computer: 500 years
• To generate 264 moves at the rate of 1 billion moves
per second
Data Structures Using C++ 2E Edited by Malak Abdullah 51
Jordan University of Science and Technology
Recursion or Iteration?
• Dependent upon nature of the solution and
efficiency
• Efficiency
– Overhead of recursive function: execution time and
memory usage
• Given speed memory of today’s computers, we can
depend more on how programmer envisions solution
– Use of programmer’s time
– Any program that can be written recursively can also
be written iteratively
Data Structures Using C++ 2E Edited by Malak Abdullah 52
Jordan University of Science and Technology
Edited by Malak Abdullah
Jordan University of Science and Technology
Summary
• Recursion
– Solve problem by reducing it to smaller versions of
itself
• Recursive algorithms implemented using recursive
functions
– Direct, indirect, and infinite recursion
• Many problems solved using recursive algorithms
• Choosing between recursion and iteration
– Nature of solution; efficiency requirements
• Backtracking
– Problem solving; iterative design technique
Data Structures Using C++ 2E Edited by Malak Abdullah 54
Jordan University of Science and Technology
Fun(5)
void fun(int a)
{
if(a<=1) Fun(3) B Fun(2) 5
cout<<"A ";
else Fun(1) B Fun(0) 3 Fun(0) B Fun(-1) 2
{
fun(a-2); A A A A
cout<<"B ";
fun(a-3);
cout<<a<<endl;
}
} A B A 3 B A B A 2 5
void main()
{
fun(5);
}
Edited by Malak Abdullah
Jordan University of Science and Technology
Fib(5)
Fib(4) + Fib(3)
int fib(int a)
{ Fib(3) + Fib(2) Fib(2) + Fib(1)
if(a==1) 1 1 0
return 0; Fib(2) + Fib(1)
if(a==2) 1 0
return 1;
return fib(a-1)+fib(a-2);
}
void main() (((1+0) + 1) + (1+0)) = 3
{
cout<<fib(5)<<endl;
}
Edited by Malak Abdullah
Jordan University of Science and Technology
void fun(int a, int b)
{ Fun(5,10)
if(a>b)
cout<<"+ "; Fun(6,8) # 5 10
if(a<=b)
{
fun(a+1, b-2); Fun(7,6) # 6 8
cout<<"# "<<a<<" "<<b<<endl;
}
} +
void main()
{
fun(5, 10);
}
+ # 6 8 # 5 10
Edited by Malak Abdullah
Jordan University of Science and Technology
