CODEWITHSUNDEEP
c++recursion
kevindang
kevindang

Reputation: 37

Calculate the function F(n) with recursion

Read the topic that I do not know what it is saying: The function F (n) determined on non-negative integers as follows: F (0) = 1; F (1) = 1; F (2n) = f (n); F (2n + 1) = F (n) + F (n + 1) Calculated F (n) by recursion. and my code:

#include<iostream.h>
double TINH_F(int n)
{
    if(n == 0)
   {
      return 0;
   }
    if(n == 1)
    {
      return 1;
    }

     return (F(n+1) - F(2*n+1));
}

Upvotes: 0

Views: 1896

Answers (3)

molbdnilo
molbdnilo

Reputation: 66371

Your last case says

  • F (n) = F (n+1) + F(2 * n + 1), for all n > 1

If you read the definition carefully, this case is not mentioned anywhere.

I believe you're being tricked by the naming of the parameter - you need four cases.

Let's break it down:

  • F (0) = 1 (or 0 - your definition says 1, but the code says 0...)
  • F (1) = 1
  • F (2n) = F (n)
  • F (2n + 1) = F (n) + F (n + 1)

The first two cases are trivial.

The third case says that if the argument - let's call it m - is even, the result is F(m/2).

The fourth case says that if the argument m is odd, the result is F(m/2) + F(m/2 + 1).
(Confirming the arithmetic left as an exercise.)

In C++:

unsigned int TINH_F(unsigned int n)
{
    if(n == 0)
    {
        return 1;
    }
    else if(n == 1)
    {
        return 1;
    }
    else if (n % 2 == 0)
    {
        return TINH_F(n / 2);
    }
    else
    {
        return TINH_F(n/2) + TINH_F(n/2 + 1);
    }
}

Upvotes: 1

Rik
Rik

Reputation: 29243

int f(int n)
{
    if (n<0) return -1; // check if n is positive
    if (n<=1) return 1; // we can catch the first two cases in a single condition

    int half = n/2;

    if (n % 2 == 0) return f(half); // if n is even
    else return f(half) + f(half+1); // if n is odd
}

Upvotes: 2

duffymo
duffymo

Reputation: 308753

This is obviously incorrect. A recursive function calls itself and includes a stopping condition:

#include<iostream.h>
double TINH_F(int n)
{
    if(n == 0)
   {
      return 0;
   }
    if(n == 1)
    {
      return 1;
    }

     // Note the function name change
     return (TINH_F(n+1) - TINH_F(2*n+1));
}

What should your function do if the integer passed in is negative? Will the recursion still work? Or should you throw an exception to indicate to callers that the contract is broken?

Upvotes: 4

Related Questions