Member Avatar for charleneok

Anyone know how to do this question?
Use recursion to implement the following recurrence relation f(x):
f(x)=1 where =1
f(x) = f((x+1)/2) +1 where x is odd
f(x) = f(x/2) +1 where x is even

This is what i did:

#include<stdio.h>

int func (int x)

int main()
{
	int x;
	printf("Please enter the value of x: ");
	scanf("%d", &x);

	int func=func(x);
	printf("%d",func) ;

	return 0;
}

int func (int x)
{
	if(x==1) 
		return 1;
	else if (x%2 ==1)
		return func ( (x+1)/2 ) + 1;
	else
		return func (x/2) + 1;
}

But it doesnt work.
Could you please kindly explain how a recursion work as well?
Thank youuuuu!

  • 4 Contributors
  • 4 Replies
  • 228 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by selina12

Dani AI

Generated

The recurrence is simple: both branches reduce x to ceil(x/2), so for integers x ≥ 1 the rule is f(x) = 1 + f(ceil(x/2)) with f(1) = 1. That means f(x) counts how many times the “halve and round up” step must be applied to reach 1. Closed form: f(x) = 1 + ceil(log2(x)). Example: 5 → 3 → 2 → 1, so f(5) = 4.

Practical fixes for the posted code: as and noted, the prototype needs a terminating semicolon (int func(int x);) or the full function should be defined before main. Also avoid shadowing the function name in main — writing int func = func(x); hides/confuses the identifier. Use a different local name (for example result) or call the function directly inside printf. Validate input (x >= 1) to avoid undefined behavior on nonpositive input.

How recursion works here: each recursive call pushes a frame and uses a strictly smaller argument (ceil(x/2) < x for x > 1), so the base case is eventually reached and the calls unwind. That guarantees termination and gives a recursion depth of O(log x), so stack depth is small. Common pitfalls: missing base case (see ’s example, which shows infinite recursion), integer-division surprises, and compiler errors from small typos. Useful debugging steps: compile with warnings enabled (e.g. -Wall -Wextra), test with small inputs and trace the sequence of arguments (temporary prints or a debugger), and fix naming/prototype issues first — after that the recursive logic will behave as expected.

Recommended Answers

All 4 Replies

Member Avatar for Stefano Mtangoo 
int func1(int x){
    //do something with int
   return func1(x-1);
}

see also and this one

Edited by Stefano Mtangoo because: n/a
Member Avatar for selina12

Inside a function when you call the same function then it is known as recursion function

Member Avatar for Greywolf333

Anyone know how to do this question?
Use recursion to implement the following recurrence relation f(x):
f(x)=1 where =1
f(x) = f((x+1)/2) +1 where x is odd
f(x) = f(x/2) +1 where x is even

This is what i did:

#include<stdio.h>

int func (int x)

int main()
{
	int x;
	printf("Please enter the value of x: ");
	scanf("%d", &x);

	int func=func(x);
	printf("%d",func) ;

	return 0;
}

int func (int x)
{
	if(x==1) 
		return 1;
	else if (x%2 ==1)
		return func ( (x+1)/2 ) + 1;
	else
		return func (x/2) + 1;
}

But it doesnt work.
Could you please kindly explain how a recursion work as well?
Thank youuuuu!

What doesn't work about it? All I see wrong with your code is a missing ";" after your function prototype.

Member Avatar for selina12

Yeah Right
Semicolon at the end of the function declaration is missing

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.