old notes

sum

#recursion #datastructures #devstudy #average #sum

The goal is to find the average of an array of integers using recursion.

This is what I have from last attempt found here: https://write.as/effyverse/recursion-101

Attempt 1:

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

Mistakes made:

__Implementation Errors: – I am calling my recursion function with the wrong input. Instead of passing in an array, I am passing in the average, fully computed.

__Understanding Errors:

  • I originally thought that my next-to-last case is represented by arr[0..count-2].sum. This is wrong because my next-to-last case is actually the ARRAY object of arr[0..count-2] and NOT the sum of it. The sum aspect is a part of the function, not the input case. It makes no sense to view the input as a sum when the method input is the array of integers — this confusion of what my input cases are supposed to be informed the implementation error above.

  • I originally thought that my base case would be the last input to be computed by the recursive function instead of thinking of it as the END of the recursive call, as the case where the recursion call is no longer needed.

Attempt 2:

Find average of array of numbers using recursion

def average(arr) count = arr.count if count == 0 0 elsif count == 1 arr[0] else sum_of_all_num = average(arr[0..count-2]) * (count-1) + arr[count-1] avg = sum_of_all_num / count end end

p average([1]) == 1 p average([0,10]) == 5 p average([1,3,5,7]) == 4

Explanation of thought process for recursion call:

What is our function? average = arr.sum / arr.count

What does this tell us? arr.sum = average * arr.count

What do we know? – If we remove the last case from our average function input and express it outside of the recursive function call, we have: sum_excl_last_num = average(arr[0..count-2]) * (count-1)

  • remembering that our goal is to find the average of all num so we need: sum_of_all_num = sum_excl_last_num + arr[count-1]

  • calculate average:
    avg = sum_of_all_num / count

  • refactor: sum_of_all_num = average(arr[0..count-2]) * (count-1) + arr[count-1] avg = sum_of_all_num / count

#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

  1. Find base case: the average of the first num in the array arr[0]
  2. Find function for base case arr[0..count-1].sum/count
  3. Find next-to-last case arr[0..count-2].sum/count
  4. Write recursion line by taking out the next-to-last case from base case average(arr[0..count-2])
  5. How is the recursion actually happening? given arr = [1,2,3,4,5] and count = 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?

Attempt 2 in follow-up to this post: https://write.as/effyverse/recursion-002