Recursion and Trees

Muhammad Fahim & Paul Sage

[Link]@[Link]
[Link]@[Link]
CSC2059 Data Structures and Algorithms
Announcement

From this lecture onwards, all material covered will be

included in Assessment 2.

2
Agenda
• Recursion and Recursive thinking
• Recursive functions
• What happens in recursive function call?
• Recursive examples
• Trees as data structures
• Trees terminology

3
Learning Outcome
• Understand and implement recursive functions
• Understand tree data structure and applications

4
 Recursion

A Set of Nested Wooden Figures

Figure Source: Chapter 7, OBJECTS, ABSTRACTION, DATA

STRUCTURES AND DESIGN USING C++ 5
Recursion
• Computer scientists in the field of artificial intelligence (AI) often use
recursion to write programs that exhibit intelligent behaviour:
• Playing games such as chess
• Proving mathematical theorems
• Recognizing patterns, and so on.

• Recursive algorithms and functions can be used to perform common

mathematical operations such as computing a factorial or a greatest
common divisor (GCD).

6
Recursive Thinking
• Recursion is a problem-solving approach that can be used to generate
simple solutions to certain kinds of problems that would be difficult to
solve in other ways.

• In a recursive algorithm the original problem is split into one or more

simpler versions of itself.

7
 General Recursive Algorithm

Figure Source: Chapter 7, OBJECTS, ABSTRACTION, DATA

STRUCTURES AND DESIGN USING C++ 8
Recursive Functions
• Suppose we write a function to calculate the sum of the first n integers (1 to n):
int Sum(int n)
{
int s = 0; // Sum of the first n integers
for (int i = 1; i <= n; i++) s += i;
return s;
}

• The above ‘big’ problem may be solved by solving a smaller problem:

int Sum(int n) Sum(n - 1)
{
int s = 0; // Sum of the first n - 1 integers
for (int i = 1; i <= n - 1; i++) s += i;

return n + s; // Add n to the partial sum to obtain the result

}
9
• So we can have a recursive implementation:
int Sum(int n)
{
if (n == 0) // The base case
return 0;
return n + Sum(n - 1); // The recursive case: the function calls itself
}
• Recursion occurs whenever a function calls itself.
• Solving problems recursively typically means that there are smaller versions of the problem
solved in similar ways.
• A recursive function must contain two cases, usually in the format:

if (base case) // where the recursion eventually stops!

// return some simple expression
else // recursive case
{
// …
// recursive call
// …
Recursion }
 Recursion – Example 1
• Example: recursive calculation of factorial
5 x 4 x 3 x 2 x 1 = 5 factorial, or 5!
• Expressed recursively: 5! = 5 x 4!
• For a general integer n > 0: n! = n x (n-1) x (n-2) x … x 2 x 1
• Recursive Definition:
n! = n x (n-1)! for n > 0
0! = 1 (mathematics definition)

// iterative solution // recursive solution

int factorial(int n) {
int factorial(int n) {
int f = 1; int i = 1;
if (n == 0) return 1;
while (i <= n) {
else return n  factorial(n - 1);
f = fi;
}
i++;
}
return f;
} 11
 Recursion – What Happens in a Function Call?
void f (int k)
• When one function calls another: {
- The current point in the calling function (f) if (k == 0)
is pushed on to stack (for returning) cout << “Finished”
else
- Space for the called function’s variables g (k-1); // What happens here?
(g) is also allocated on stack // Rest of f…
}
• When the called function ends:
- The space for its variables stack is released (popped) void g (int p)
- The return point for execution (in f) is popped from stack. {
int temp;
Execution continues from f.
// rest of g …
}

• In this simple case, we could have only one uncompleted function call stacked up.

12
 Recursion – What Happens in Recursion?
• When a function calls itself, rather than another function: void f (int k) {
This is handled in exactly the same way if (k == 0)
cout << “Finished”
else
f (k-1);
• Suppose we call: f(3) }

- This will call f(2), which will call f(1), which will call f(0), which will print “Finished”.
- At this point, we have four return addresses in stack, and four calls still unfinished
- First to finish will be f(0); then f(1) is resumed, and it finishes.
- Then f(2) is resumed, and finishes.
- Finally, f(3) is resumed, and finishes.
• But if we call: f(-1) i.e., no catching base case ???
This will go on for ever, in theory, with an infinite number of uncompleted calls stacked up.
• In practice, until we run out of memory for the stacks, or we get integer underflow.

13
Recursion – Example 2
• Recursive function for finding the length of a string
#include <iostream>
using namespace std;

int stringLength(string& str, int index = 0) {

// Base case: if the index reaches the end of the string, return 0
if (index == [Link]())
return 0;

// Recursive case: move to the next character and add 1

return 1 + stringLength(str, index + 1);
}
int main() {
string myString = "Data structures and Algorithms";
// Call the recursive function
int length = stringLength(myString);
cout << "Length of the string: " << length << endl;
cout << "Cross-check your recursive function: " << [Link]();
return 0;
}
14
 Example 2
• Trace of size("ace") • Run-time stack after all calls

Figure Source: Chapter 7, OBJECTS, ABSTRACTION, DATA

STRUCTURES AND DESIGN USING C++ 15
Recursion – Example 3
• Recursive function for string is displayed in reverse, one character per line.
#include <iostream>
using namespace std;
void print_chars_reverse(string str) {
if (str == "") {
return;
}
else {
print_chars_reverse([Link](1));
cout << [Link](0) << endl;
}
}
int main() {
// Declare a string
string myString = "ace";

// Call the function to print the string in reverse

cout << "Reversed characters:" << endl;
print_chars_reverse(myString);

return 0;
} 16
 Trees as Data Structures
• Trees are useful for representing hierarchical structure in real life applications

Example 1
The hierarchical management
structure of a system
(e.g., a large organisation) QUB

Science & Arts &

Medicine
Engineering Humanities

EEECS CCE MAE

17
 Tree
• Trees are useful for representing hierarchical structure in real life applications

Example 2
The language structure
of linear text (natural or
THE DOG BITE THE MAN
computer languages)
Sentence

Subject Predicate

Article Noun Verb Object

THE DOG BITE Article Noun

THE MAN
18
 Sentence Hypotheses Lexicon

this is speech

it is not easy
..
. Word / phoneme string hypothesis

he is never here th ih s ih z s p iy ch

..
.
Example 3
Trees are used to build an
automatic speech recognition
Layer N
(ASR) system
DNN
Layer 2

Layer 1

Unknown
speech
Trees
 Tree Terminology
* The nodes (B, C) directly below a node (A) are called
the (direct) descendants of A.
* A is called the (direct) ancestor of B, C.
* The top node (A) which has no ancestor is called the root. A general tree
* A node (e.g. J) which has no descendants is called a leaf.
* Each node, apart from the root, has exactly one ancestor. A binary tree

* A binary tree is a tree in which every node has at most

two descendants.
* A binary tree node comprises:
a data item, a left subtree, and a right subtree
* A binary tree is therefore a recursive data structure.
* The depth (or height) of a binary tree is the number of levels:
depth(tree) = 1 + max {depth([Link] subtree), depth([Link] subtree)}
Q&A

21