Member Avatar for dilip.mathews

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????

  • 6 Contributors
  • 6 Replies
  • 260 Views
  • 2 Years Discussion Span
  • Latest Post Latest Post by tux4life

Dani AI

Generated

— good question, and 's prompt ("how many recursive calls?") is exactly the right way to think about it. Precisely: calling fact(n) runs the recursive step for n, n-1, ..., 1 and finally the base case 0, so there are n+1 activations (depth = n+1). That linear-depth chain is why the naive recursive implementation uses a linear amount of stack space and performs a linear number of multiplications.

Two practical points that weren't explicit in the thread:

  • Tail recursion can avoid the extra stack in languages or compilers that perform tail-call elimination. Converting factorial to a tail-recursive form (carry an accumulator) yields a call that can be optimized into a loop by some compilers/runtime. C example (tail form):
long long fact_tail(long long n, long long acc) {
    if (n == 0) return acc;
    return fact_tail(n - 1, acc * n);
}

long long fact(long long n) {
    return fact_tail(n, 1);
}
  • In CPython there is no tail-call optimization and there is a recursion depth limit, so the tail-recursive form still uses O(n) stack there. Example iterative form (safe in Python and C):
def fact_iter(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

A final caveat: if you measure cost more strictly (bit-complexity), each multiplication cost grows as the factorial grows, so computing exact n! for very large n costs more than just "n multiplications" in a constant-time model. For everyday use, pick the iterative version for large inputs or when you need to avoid stack limits; use tail recursion only when you know the language/runtime will optimize it. was right to confirm the linear behaviour, but the nuance above is important in real-world code.

Recommended Answers

All 6 Replies

Member Avatar for dilip.mathews

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)

Member Avatar for Rashakil Fol

That's right.

Member Avatar for salie_90

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

commented: Congratulations for resurrecting a dead thread! -2
Member Avatar for Deque

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.

Member Avatar for tux4life

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

Don't resurrect old threads to just ask your question, you've already your own thread here:
http://www.daniweb.com/forums/post906282.html.

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.