CODEWITHSUNDEEP
cfunctionrecursion
unintendedjoy
unintendedjoy

Reputation: 289

How does recursive function in C works

Function fun(n) is defined as such:

fun(n) = 1                 (if n <=1)
fun(n) = fun(n/2)          (if n is even)
fun(n) = 2*fun((n-1)/3)    (if n> and n is odd)

I'm trying to write a recursive function to compute and return the result. I just started learning recursion, I got kind of lost while doing this function. Can someone correct me and explain to me? Thanks!

Here's what I did:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
#include <math.h>

int fun(int n);

int main()
{
    int num;

    printf("\nEnter a number: ");
    scanf("%d", num);
    printf("Result = %d\n", fun(num));
    return 0;
}

int fun(int n)
{
    if (n <= 1)
    {
        return 1;
    }

    else if (n % 2 == 0)
    {
        return fun(n / 2);
    }

    else if ((n > 1) && (n % 2 == 0))
    {
        return 2 * fun((n - 1) / 3);
    }
}

Expected output:

Enter a number: 13
Result = 2

Enter a number: 34
Result = 4

Output I'm getting instead:

Enter a number: 13
Result = 1

Enter a number: 34
Result = 1

Upvotes: 4

Views: 392

Answers (5)

ctutte
ctutte

Reputation: 131

I think last if should be:

else if ((n > 1) && (n % 2 != 0))

Notice the != instead of ==.

Upvotes: 1

Wojtek Surowka
Wojtek Surowka

Reputation: 21003

The third condition

else if ((n > 1) && (n % 2 == 0))

is wrong, but instead of fixing it just you else no else if - because all other conditions were checked already.

Upvotes: 0

Arkku
Arkku

Reputation: 42159

scanf takes a pointer to int as argument for %d, i.e.,

scanf("%d", &num);

Also, your function fun does not handle all cases and may fall off the bottom:

if (n <= 1)
{
    return 1;
}
else if (n % 2 == 0)
{
    return fun(n / 2);
}
else if ((n > 1) && (n % 2 == 0))
{
    return 2 * fun((n - 1) / 3);
}

The last else if condition is never met, because the previous check for n % 2 == 0 already returns in that case. Also the n > 1 is pointless because the first n <= 1 returns in all other cases.

You can simply make it:

else
{
    return 2 * fun((n - 1) / 3);
}

Upvotes: 6

Steve Cox
Steve Cox

Reputation: 2007

The condition that n is odd is written wrong here. You wrote the same thing as for when n is even.

Its probably better to explicitly make the cases disjoint so you always return and there's no warning, like this:

int fun(int n)
{
    if(n <= 1)
        return 1;
    if(n % 2 == 0)
        return fun(n/2);
    //No need for a condition, we know the last one must be satisfied
    return 2 * fun((n-1)/3);
}

or, add another "default" case that indicates there was some error.

Upvotes: 1

Green goblin
Green goblin

Reputation: 9994

The culprit is the last else if condition. Change it to: 

else if ((n % 2) != 0)

Upvotes: 2

Related Questions