recursion in computer science

[donohoe147]

hi

struggling with this problem, don't understand the topic

 

recursion

 

 

Exercise 3.

Let f(n) = f(ceiling n/2)+n, and let g(n) = g(n􀀀1)+2n with g(1) = 0. Calculate

the following values by unfolding.

1. f(5) 2. f(9)

3. g(6) 4. g(9)

any advice or help would be appreciated

 

regards

 

 

 

im not looking for answers just a bit of advice or an example.

i have james hein s book on discrete maths , logic and computability

[timo]

What exactly is your problem here? Recursion as such? Take this example (in laymen-c++), then:

 

Example: The factorial f(n) of a natural number n is defined as f(0)=1, and f(n)=n*f(n-1) for n>0. Calculate f(i) for i=0...5. A solution would be

#include <iostream>

int f(int n) {
 if (n==0) 
   return 1; 
 else 
   return n*f(n-1);
}

int main() {
 for (int i=0; i<=5; ++i) 
   std::cout<<"f("<<i<<")="<<f(i)<<std::endl;
}

 

Try to understand what this code does (the magic trick is that the function f(n) calls itself); your examples should be straightforward extensions, then (though one letter did not render and your function g reads "g(n) = g(n?1)+2n" for me).

 

Caveat: I don't know what "unfolding" is (in case it is a specialized technical term), so possibly above example is not what you are looking for (but it's recursion, at least). But you can probably figure that our yourself.