CPSC 5005

Data Structures
Yueting Chen
Recursion
Problem: Sum of an Array

• How do you compute the sum of an array?

int sum_iterative(const int arr[], int n) {

int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
} Is this the only way?
Problem: Sum of an Array

• Anther way to look at the problem:

• The sum of n elements =
• the sum of the first n-1 elements + the value of the last element.
• Assume we define sum(int arr[], int n), for a given array A

sum(A, n) = sum(A, n-1) + A[n-1]

The sum of the first The value of the last
n-1 elements element in A

1 3 6 8 1 3 6 8
Problem: Sum of an Array
int sum(const int arr[], int n) {
• Will this work? return sum(arr, n - 1) + arr[n - 1];
}

• Missing stop condition! We should stop when n=1

• Base case: when n=1, return arr[0]
Base Case
int sum(const int arr[], int n) {
if (n == 1) {
return arr[0];
}
return sum(arr, n - 1) + arr[n - 1]; Recursive Case
}
Recursion

• Recursion occurs when a function refers to itself in its own definition.

• Recall our sum problem:
• Base case (stop condition): n=1, sum(arr, n)=1
• Recursive case: n>1, sum(arr, n) = sum(arr, n-1) + arr[n-1]
• Recursion can also be defined in mathematical equations:

𝐴0 if 𝑛 = 0
𝑠𝑢𝑚 𝐴, 𝑛 = ቊ
𝑠𝑢𝑚 𝐴, 𝑛 − 1 + 𝐴 𝑛 − 1 if 𝑛 ≥ 1
Recursion Trace
int sum(const int arr[], int n) {
• A={4,3,6,2,5}, n=5 if (n == 1) {
return arr[0];
sum(A, 5) }
return 15+A[4]=15+5=20 return sum(arr, n - 1) + arr[n - 1];
}

sum(A, 4)
return 7+A[2]=7+6=13

sum(A, 3)
return 4+A[1]=4+3=7

sum(A, 2) Let’s visualize it:

return A[0]=4
• [Link]
[Link]#mode=edit
sum(A, 1)
Recursion Trace

• Stack Frames are the key

• A new stack frame is created for each function call.
• Contains a copy of all local variables and parameters for that call.
• Remains on the stack until the function returns, then it is destroyed
(automatically).
• [Link]
 Question: Sum of an Array

• What if you define

• The sum of n elements =
• The sum of the first element + the value of the last n-1 elements?
• How can you write the formulation and the code?
int sum(const int arr[], int n, int i = 0) {
if (i == n) {
0 if 𝑛 = 𝑖 return 0;
𝑠𝑢𝑚 𝐴, 𝑛, 𝑖 = ቊ
𝐴 𝑖 + 𝑠𝑢𝑚 𝐴, 𝑛, 𝑖 + 1 if 𝑖 < 𝑛 }
return arr[i] + sum(arr, n, i + 1);
}
Initially, i =0
Exercise: Factorial Function

• Factorial function:
1 if 𝑛 = 0
• 𝑓 𝑛 = 𝑛! = ቊ
𝑛 ∙ 𝑛 − 1 ∙ 𝑛 − 2 ∙∙∙ 3 ∙ 2 ∙ 1 if 𝑛 ≥ 1
• 1! = 1
• 2! = 2 ∗ 1
• 3! = 3 ∗ 2 ∗ 1
• 4! = 4 ∗ 3 ∗ 2 ∗ 1
• Can you rewrite it in recursive form?
Exercise: Factorial Function

• Factorial function:
1 if 𝑛 = 0
• 𝑓 𝑛 = 𝑛! = ቊ
𝑛 ∙ 𝑛 − 1 ∙ 𝑛 − 2 ∙∙∙ 3 ∙ 2 ∙ 1 if 𝑛 ≥ 1
• Can you rewrite it in recursive form?
int factorial(int n) {
1 if 𝑛 = 0 if (n == 0) {
•𝑓 𝑛 =ቊ return 1;
𝑛 ∙ 𝑓 𝑛 − 1 if 𝑛 ≥ 1 }
• In C++ code? }
return n * factorial(n - 1);

• Visualize it to obtain recursion trace

[Link]

• [Link]
Fibonacci Sequence

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….

• Do you observe the pattern?

Fibonacci Sequence

• Fibonacci Sequence
• 𝑓𝑖𝑏(0) = 0;
• 𝑓𝑖𝑏(1) = 1; Looks familiar?
• 𝑓𝑖𝑏(2) = 1; • Recursive Pattern!
• 𝑓𝑖𝑏(3) = 2 = 1 + 1 = 𝑓𝑖𝑏(1) + 𝑓𝑖𝑏(2);
• Can you write it down in
mathematical formulation?
• 𝑓𝑖𝑏(4) = 3 = 1 + 2 = 𝑓𝑖𝑏(2) + 𝑓𝑖𝑏(3);
• 𝑓𝑖𝑛(5) = 5 = 2 + 3 = 𝑓𝑖𝑏(3) + 𝑓𝑖𝑏(4);
•…
Fibonacci Sequence

• Mathematical form:
0 , if 𝑛 = 0 Base Cases
• 𝑓𝑖𝑏 𝑛 = ቐ 1 , if 𝑛 = 1
𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏 𝑛 − 2 , if 𝑛 > 2 Recursive Cases
• In C++?
int fib(int n) {
if(n <= 1){ //Base Case
return n;
}
else{ //Recursive Case
return fib(n-1) + fib(n-2);
}
}
Recursion Trace

• Can you draw the recursion trace for fib(5)?

int fib(int n) {
if(n <= 1){ //Base Case
return n;
}
else{ //Recursive Case
return fib(n-1) + fib(n-2);
}
}
Recursion Trace

• Two main shapes of recursion trace in the above three problems.

sum(A, 5)
return 15+A[4]=15+5=20

sum(A, 4)
return 7+A[2]=7+6=13

sum(A, 3)
return 4+A[1]=4+3=7

sum(A, 2)
return A[0]=4
sum(A, 1)
Recursion Types

• Linear recursion 1 if 𝑛 = 0
𝑓 𝑛 =ቊ
• A function is defined with at most one recursive call. 𝑛 ∙ 𝑓 𝑛 − 1 if 𝑛 ≥ 1
• Binary recursion
• A function is defined with at most two recursive calls. 0 , if 𝑛 = 0
𝑓𝑖𝑏 𝑛 = ቐ 1 , if 𝑛 = 1
• Multiple recursion 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏 𝑛 − 2 , if 𝑛 > 2
• A function is defined with multiple recursive calls.
[Exercise] Binary Recursion

• Can you rewrite the function sum with binary recursion?

𝐴0 if 𝑛 = 0
𝑠𝑢𝑚 𝐴, 𝑛 = ቊ
𝑠𝑢𝑚 𝐴, 𝑛 − 1 + 𝐴 𝑛 − 1 if 𝑛 ≥ 1

• Tips:
• To use binary recursion, the sum function needs to be called twice in one
invocation.
• Can you divide the array into two sub-arrays?
[Exercise] Binary Recursion

• Can you rewrite the function sum with binary recursion?

• Step 1
1 i=0, n=1
1 3 • We needs to compute part of the
3
array with a given start index and
i=1, n=1
1 3 6 8 i=0, n=2 length (# of elements to compute).

6 8 6 i=2, n=1
𝑠𝑢𝑚(𝐴, 𝑖, 𝑛)
i=2, n=2 8 i=3, n=1
Start index # of elements
to compute
[Exercise] Binary Recursion

• Can you rewrite the function sum with binary recursion?

• Step 2:
1 i=0, n=1
1 3 • Recursive step: reduce the size of the
3 i=1, n=1 current array by half to form two
1 3 6 8 i=0, n=2
arrays, and compute each part
6 8 6 i=2, n=1 separately

8
• New # of elements to compute for
i=2, n=2 i=3, n=1
𝑛 𝑛
each part: and 𝑛 −
2 2
𝑛 𝑛 𝑛
𝑠𝑢𝑚 𝐴, 𝑖, 𝑛 = 𝑠𝑢𝑚 𝐴, 𝑖, ⌊ ⌋ + 𝑠𝑢𝑚(𝐴, 𝑖 + ⌊ ⌋, 𝑛 − ⌊ ⌋)
2 2 2
[Exercise] Binary Recursion

• Can you rewrite the function sum with binary recursion?

• Step 3:
1 i=0, n=1
1 3 • Find the base case:
3 i=1, n=1
1 3 6 8 i=0, n=2 • When 𝑛 = 1, produce 𝐴 𝑖

6 8 6 i=2, n=1
𝑠𝑢𝑚 𝐴, 𝑖, 𝑛 = 𝐴[𝑖], when 𝑛 = 1
i=2, n=2 8 i=3, n=1

𝑛 𝑛 𝑛
𝑠𝑢𝑚 𝐴, 𝑖, 𝑛 = 𝑠𝑢𝑚 𝐴, 𝑖, ⌊ ⌋ + 𝑠𝑢𝑚(𝐴, 𝑖 + ⌊ ⌋, 𝑛 − ⌊ ⌋), when 𝑛 > 1
2 2 2
[Exercise] Binary Recursion

• Put them all together

𝐴[𝑖] , if 𝑛 = 1
• 𝑠𝑢𝑚 𝐴, 𝑖, 𝑛 = ቐ 𝑛 𝑛 𝑛
𝑠𝑢𝑚 𝐴, 𝑖, + 𝑠𝑢𝑚 𝐴, 𝑖 + ,𝑛 − , if 𝑛 > 1
2 2 2

• In C++?
[Exercise] Binary Search

• Write implementation for binary search.

• Given an array of integers in increasing order, find if an element x exists in
the array
• Questions:
• How do define the function?
• What are the base case and recursive steps?
[Exercise] Binary Search

• Define function 𝑏𝑠 𝐴, 𝑥, 𝑖, 𝑛
Array Value to search Start index end index
• Recursive case:
𝑖+𝑛 Can you write the C++ code?
•𝑚=
2
• If 𝑥 < 𝐴[𝑚]: search the left part, otherwise, search the right part.
• Base case:
• Stops when 𝑖 > 𝑛 (out of elements, not found) or 𝐴[𝑚] = 𝑥 (found)
[Exercise] Count Nodes in Linked List

• Write implementation for a function that

• Counts the # of nodes in a singly linked list.
• Questions:
• How to define the function?
• What are the base case and recursive steps?
[Exercise] Count Nodes in Linked List

• Node Definition
int countNodes(Node* head){
if (head == nullptr)
return 0;
else
return 1 + countNodes(head->next);
}
 Exercise: Reverse Linked List

• Write a recursive function to reverse a singly linked list.

head
1 2 3 4 5

head

1 2 3 4 5

[Link]
[R] Resources
• Chapter 3.5
• Open DSA Recursion Exercises
• [Link]
[Link]/OpenDSA/Books/Everything/html/Code
[Link]
• Video “5 simple steps to solve any recursive
problem”:
• [Link]
• Visualization tool
• [Link]