Member Avatar for thehakan

int p(int x)
{ if(x<3)
return x;
else
return p(x-1) * p(x-3);
}

say m(x) is a number of multiplication operations that the execution of p(x) performs.
what can be recursive definition of m(x)??

Answer should be (x-1)*(x-3) . Am I wrong?

  • 2 Contributors
  • 2 Replies
  • 114 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by thehakan

Dani AI

Generated

was correct in spirit. In plain words: the base cases (x < 3) perform no multiplications, and every non‑base call does one multiplication plus whatever multiplications its two recursive subcalls do. That verbal recurrence is the right way to count operations; the algebraic guess by , (x-1)*(x-3), is not correct (simple counterexamples show the mismatch).

Some concrete values (number of multiplications for x = 0..12):
0, 0, 0, 1, 2, 3, 5, 8, 12, 18, 27, 40, 59.
So m(3)=1 (not 0), m(6)=5 (not 15), etc. The sequence is built by adding the counts from the x-1 and x-3 subcalls and the single multiplication at the current call, which produces the numbers above.

A useful rewrite: set h(x) = m(x)+1. Then h satisfies a homogeneous linear recurrence with constant coefficients (h(x) = h(x-1) + h(x-3)) and initial values h(0)=h(1)=h(2)=1. The characteristic equation is r^3 - r^2 - 1 = 0; its dominant real root is about 1.46557, so m(x) grows exponentially like Theta(1.4656^x).

Practical note: the naive recursion repeats work heavily. Using memoization or a bottom‑up DP reduces the number of multiplications to O(x) — specifically one multiplication for each integer from 3 up to x (i.e., x-2 when x>=3). Also, with the original base returns (return x for x<3) the function values themselves become 0 for all x>=3, but the naive recursion still does all the redundant multiplications unless you cache results.

Recommended Answers

All 2 Replies

Member Avatar for perniciosus

m(x) = x < 3 ? 0 : m(x - 1) + m(x - 3) + 1

Member Avatar for thehakan

thank u

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.