Define the following:
- Recursion
- Recursion describes a method that calls itself.
- Recursive Case
- A recursive case is the part of the method where recursion occurs.
- Base Case
- Base case returns a value without making a recursive call. This is what recursive cases should be bringing us closer to.
- Activation Chain/Stack
- An Activation chain/stack is the entire process of solving the recursive method and getting the appropriate answer.
- Activation Record/Call
- An activation record/call is each little "bubble" within the activation chain. I take that to mean that an activation record occurs each time a recursive case occurs within an activation chain.
- Infinite Recursion/Stack Overflow/Stack too deep
- Infinite recursion occurs when the recursive cases are not leading to a base case.
- Tail Recursion
- Tail recursion occurs when the last computation within a method is a recursive call. All our recursive methods from the homework are examples of Tail recursion.
def mystery1(n)
if n == 1
return n
else
return n + mystery1(n-1)
end
end
- What is mystery1(5)?
- 15
- What is mystery1(10)?
- 55
- What is mystery1(0)?
- stack level too deep Meaning: The number and all of the numbers before it added together. Example: mystery1(5) = 5 + 4 + 3 + 2 + 1 = 15
def mystery2(n)
if n < 10
return n
else
return (n%10) + mystery2(n/10)
end
end
- What is mystery2(123)?
- 6
- What is mystery2(9005)?
- 14
- What is mystery2(-123)?
- -123
- Added Fun: How could we make
mystery2(-123)
work the way we might expect it to work instead of the way it does?- Set the following condition: if n==0, return n Meaning: All of the separate digits of the number added together. Example: mystery2(123) = 1 + 2 + 3 = 6
def mystery3(n)
if n == 0
return 100
elsif n == -1
return 200
end
if n%2 == 0
return mystery3(n/2)
else
return mystery3(n-1)
end
end
- What is mystery3(1)?
- 100
- What is mystery3(13)?
- 100
- What is mystery3(-6)?
- stack level too deep (checked my answer and found out I had it wrong. Worked on it until I got the correct answer: 200)
def mystery4(b,e)
if e == 0
return 1
else
return b * mystery4(b,e-1)
end
end
- What is mystery4(10,2)?
- 100
- What is mystery4(4,3)?
- 64
- What is mystery4(5,0)?
- 1 Meaning: b^e Example: mystery4(10,2) = 10^2 = 100
def mystery5(s)
if s.length == 0
return ""
else
return "*" + mystery5(s[1..-1])
end
end
- What is mystery5("hi")?
- "**"
- What is mystery5("")?
- ""
- What is mystery5("Hi, there!")?
- "**********"
- Added Fun: How could we make only alphabetic characters to be changed to stars?
- Use regex to check the char type. Meaning: All chars in string replaced with *
def mystery6(s)
if s == nil || s.length == 0
return ""
else
space = 0
until space >= s.length || s[space] == " "
space += 1
end
return mystery6(s[(space+1)..-1]) + " " + s[0...space]
end
end
- What is mystery6("goodnight moon")?
- " moon goodnight"
- What is mystery6("Ada Developers Academy")?
- " Academy Developers Ada"
- What is mystery6("Hi, there!")?
- " there! Hi,"
- Added Fun: How could we make the reversal happen by letter, instead of by word (i.e. Make it so that mystery6("goodnight moon") returned "noom thgindoog")?
- I am not sure. :( Meaning: All words in the string are reversed in order and a space is added in the front