2018-04-09

posted Apr 8, 2018, 6:27 AM by Konstantinovich Samuel   [ updated Apr 9, 2018, 6:34 AM ]
Recursion

For each problem below:
a. Write the base case.
   e.g. When n is 0 the result is 0.
b. Write out the recursive relationship. (hint: start with numbers and then do it in terms of n)
    e.g.   fib(n)  is   fib(n-1) + fib(n-2)
c. Write the function in idle. Test it (start with base cases and work your way up)

1. Triangle numbers:
We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. 
This is a size 5 triangle:
*
**
***
****
*****
Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows. 

triangle(0) → 0 
Because there are no rows. 

triangle(1) → 1 
Because it is just:
*

triangle(2) → 3
Because it is just:
*
**

2. Consider a function powerN(base,n) where you are given base and n that are both positive integers. 
You must compute recursively (no loops) the value of base to the n power, so powerN(5, 2) is 25 (5 squared). 

powerN(3, 1) → 3 
powerN(3, 2) → 9 
powerN(3, 3) → 27

3. Given a string, compute recursively (no loops) a new string where all the lowercase 'x' chars have been changed to 'y' chars. 
hint: Think of string concatenation to be just like addition, you can say   return "y" + function( value)  
changeXY("codex") → "codey" 
changeXY("xxhixx") → "yyhiyy" 
changeXY("xhixhix") → "yhiyhiy"

4. Given a non-empty list of integers, compute recursively the number of times that the value 11 appears in the list. 
We'll use the convention of considering only the part of the array that begins at the given index. 
In this way, a recursive call can pass index+1 to move down the array. 
The initial call will pass in index as 0. 

Do not modify the list! 

Hint: the base case has 2 options!

array11([4], 0) → 0  
array11([11], 0) → 1
array11([1, 2, 11], 0) → 1 
array11([11, 11, 3], 0) → 2 
array11([11, 11, 3], 1) → 1  #because you are looking starting at index 1!
array11([1, 2, 3, 4], 0) → 0

To see how this can be used, remember that the 2nd parameter is the place you are looking at now so:
array11([11, 2, 11, 11, 11], 0) → 4  #start by looking at the 0th index.
array11([11, 2, 11, 11, 11], 1) → 3  #start by looking at the 1st index. (This would be used in the previous call)
array11([11, 2, 11, 11, 11], 2) → 3
array11([11, 2, 11, 11, 11], 3) → 2
array11([11, 2, 11, 11, 11], 4) → 1



Comments