CSCI 3110

Recursion Exercises

< Previous  Next >

1. What does the acronym GNU mean?
2. What are the four questions for constructing recursive solutions?
3. Apply the four questions for constructing recursive solutions to printing a string backwards:
4. Apply the four questions for constructing recursive solutions:
   if( M-Number % 10 < 3){
           Write a recursive function to print out the contents of a linked list.
   }else if( M-Number % 10 < 7){
           Write a recursive function to calculate a Fibonacci number:
           F_n = F_{n - 1} + F_{n - 2} and F₁ = 1 and F₂ = 1.
   }else{
           Write a recursive binary search. Look at the middle element of an array.
           If the number you're searching is larger than the middle element, search the upper half.
           If the number you're searching is smaller than the middle element, search the lower half.
           Otherwise, the number is found.
   }
   
5. Tower of Hanoi
   • Interactive Game
   • Code
6. n choose k (binomial coefficients):
   For any set containing n elements, the number of distinct k-element subsets
   Arranging binomial coefficients into rows for successive values of n, and in which k ranges from 0 to n, gives a triangular array called Pascal's triangle.

   ( n )   ( n-1 )   ( n-1 )
   (   ) =	(     ) + (     ) for 1 <= k <= n - 1				
   ( k )   ( k-1 )   (  k  )
   
   ( n )   ( n )
   (   ) =	(   ) = 1  for n >= 0 			   
   ( 0 )   ( n )
   

Last Modified: