Hi all,

Can anybody tell me how to calculate the order of a recursive function.
Lets take factorial function.

Without using recursion

int x =1;
for(int i = 1;i<=n;i++)
x = x*i;

In this case the order will the O(n) in terms of time and in terms of space it will be O(1).
Assuming I am right. Correct me otherwise.

Now suppose I implemet the same factorial with rtecursion

return(n==0? 1 : n * fact(n-1));

What will be the order in time and space????

## All 6 Replies

Well for a value of 'n', how many recursive calls will there be?

There will be n recursive calls, so the order will be O(n ) for time complexity. Am i right?
In that case space complexity will also be of O(n)

That's right.

i need help please...i ask, to make a program that accepts a positive integers and displays all odd number between 1 to the integer entered (inclusive) accept the integer in main() and use a recursive function to identify and display the odd numbers.

tnx..salie

i need help please...i ask, to make a program that accepts a positive integers and displays all odd number between 1 to the integer entered (inclusive) accept the integer in main() and use a recursive function to identify and display the odd numbers.

What have you done by now?
We can help you, but I assume, that no one writes the hole program for you. So try by yourself und ask about concrete problems.

i need help please...i ask, to make a program that accepts a positive integers and displays all odd number between 1 to the integer entered (inclusive) accept the integer in main() and use a recursive function to identify and display the odd numbers.

tnx..salie