Recursion 003

#recursion #datastructures #devstudy #balancedparenthesis #boolean

The Problem:

Write a method that accepts a string containing open or closed parenthesis and returns true if the string has a balanced set of parenthesis. Use recursion.

Using the 10DIME approach to understanding the problem:

Input: a string of parenthesis

Output: boolean. true if balanced, false if not balanced

Definitions: – balanced means that the string has the same amount of left brackets as right brackets – not balanced means that there is an uneven amount of brackets

Instructions:

1. make string an array and remove the commas

Planning out Iterative Function instructions: 2. IF ODD: I want to split the string into characters, check if there is an odd total amount of chars, if so, return false 3. IF EVEN: I could: – iterate through, collect all left brackets, save the count – collect all right brackets, save the count – if they are the same, return true

Planning Out Recursion Function Instructions:

• I realized that I didn't need to remove the commas from the input string if my input just didn't have commas to begin with. The original problem did not say there would be commas so I need to think more carefully about the question next time.

1. Base case: there are zero elements left. arr.empty? 2. Function: What is the repetition required to solve this problem? compare one element to the next and if they do not match, remove both: arr.each_with_index do

`if arr[0] != arr[1] # remove both

3. Next-To-Last Case: arr[0..c-3] 4. Recursion Function: compare[0..c-3] where compare is a function that compares the first and the second item in an array. If they are not equivalent, both items are deleted.

So this is what I want to repeatedly call:

def compare(array) if array[0] != array[1] array.delete_at(0) array.delete_at(1) else (reduce size until base case is met) end end

5. What does this look like when the program is running?

Given an array of elements: arr = [x0, x1, x2, x3, x4, x5] 1. The first call will compare x0 != x1, let's say this is true so those elements are removed from array. So we can say that [x0,x1,x2,x3,x4,x5] == [x2, x3, x4, x5].push(x0,x1) where we call the recursion on [x2, x3, x4, x5] part

1. [x2, x3, x4, x5] == [x4, x5].push(x2, x3)

2. [x4, x5] == [].push(x4, x5)

3. [].empty? is our base case = code finished.

Methods: N/A

Edge Cases: – if array is empty – if array only contains one type of bracket

ITERATIVE IMPLEMENTATION:

def is_balanced?(string) return false if string.empty? arr = string.chars.delete_if { |s| s == "," } if arr.count.odd? false else left = [] arr.each do |bracket| if bracket == "(" left << bracket arr.delete(bracket) end end left.count == arr.count ? true : false end end

p is_balanced?("") == false p is_balanced?("(") == false p is_balanced?("(,)") == true p is_balanced?("(,(,(,),)") == false p is_balanced?("(,(,(,(,(") == false p is_balanced?("(,(,(,),),)") == true

recursion implementation: NOT COMPLETED

def is_balanced?(input) return false if input.empty?

input.class == Array ? input : input = input.chars

count = input.count return false if count == 1

if count == 2 if input[0] != input[1] return true else false end elsif count > 2 return false if input.uniq.size == 1 input.each_cons(2) do | first, second | if first != second input.delete_at(0) input.delete_at(1) is_balanced?(input) else is_balanced?(input.shuffle) end end end end

p is_balanced?("") == false p is_balanced?("(") == false p is_balanced?("()") == true p is_balanced?("((") == false p is_balanced?("((())") == false p is_balanced?("(((((") == false p is_balanced?("((()))") == true

#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