Recursion 001
#recursion #datastructures #devstudy #sum #average
Problem 1: find sum using recursion
How to Approach the Problem:
1. Find base case:
establish base condition of arr.count == 1
def sum(arr)
count = arr.count
if count == 1
return arr.sum
2. Find the function for the base case:
arr.sum or arr[0..count-1].sum is our base case because we have added up all the numbers in the array
3. Find the next-to-last case:
arr[0..count-2].sum is our next-to-last case because we are adding up all the numbers in the array minus the last element
4. Write the recursion line by taking out the next-to-last case from the base case:
We want to take out arr[count-1] from the recursion line so that we have: recursive function call + arr[count-1] so we now have:
sum(arr[0..count-2]) + arr[count-1]
This means that we are getting the sum of the first to next-to-last numbers in the array through the recursive call and then adding to that the value of the last array number.
5. How is the program actually doing this?
Given arr = [1,2,3,4,5], we can express this with recursion call + second-to-last case to get our:
first recursion call: [1,2,3,4,5].sum = [1,2,3,4].sum + 5
Then we want to express `[1,2,3,4].sum] with with recursion to get:
second recursion call: [1,2,3,4].sum = [1,2,3].sum + 4
Continue until base case:
third recursion call: [1,2,3].sum = [1,2].sum + 3
fourth case: [1,2].sum = [1].sum + 2
base case: [1].sum = 1 and algorithm completed!
Solution:
def sum(arr)
count = arr.count
if arr.count == 1
arr[0..count-1].sum
else
sum(arr[0..count-2]) + arr[count-1]
end
end
Rewrite Solution in more rubyist way: TBD
Problem 2: Find average using recursion
First attempt:
using recursion
- Find base case: the average of the first num in the array
arr[0] - Find function for base case
arr[0..count-1].sum/count - Find next-to-last case
arr[0..count-2].sum/count - Write recursion line by taking out the next-to-last case from base case
average(arr[0..count-2]) - How is the recursion actually happening?
given arr = [1,2,3,4,5]andcount = arr.count
[1,2,3,4,5].sum / count is the same as: [1,2,3,4].sum / count-1 * 5
[1,2,3,4].sum / count is the same as: [1,2,3].sum / count-1 * 4
[1,2,3].sum / count is the same as: [1,2].sum / count-1 * 3
[1,2].sum / count is the same as: [1].sum / count-1 * 2
[1].sum / count is the same as: 1 so our base condition has been met!
Implementation
def average(arr)
count = arr.count
if count == 1
arr[0..count-1].sum/count
else
average(arr[0..count-2].sum / (count-1)) * arr[count-1]
end
end
a = [1,2,3,4,5]
p average(a) == 3
b = [0,10]
p average(b) == 5
c = [1]
p average(c) == 1
Mistake made: The input that I'm passing into my recursive call is not an array but an integer value so the program does not work since it is expecting an array.
Attempt 2: NOT YET COMPLETED
- How do I represent the part of the averaging function that divides by the total count?
- it needs to be in the recursive function call but how?