"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { code: "code", h3: "h3", li: "li", ol: "ol", p: "p", pre: "pre", span: "span", strong: "strong", table: "table", tbody: "tbody", td: "td", th: "th", thead: "thead", tr: "tr", ul: "ul", ..._provideComponents(), ...props.components }, {Analogy, Answer, Assessment, BlockDiagram, CodeBlock, ComparisonTable, ContentAttribution, DefinitionEntry, DefinitionGroup, English, Explanation, FormulaBox, Hinglish, ImportantQA, KeyPoints, MCQ, MermaidDiagram, Practical, Prompt, QAQuestion, SubTopicHeader, Theory, TopicOverview} = _components; if (!Analogy) _missingMdxReference("Analogy", true); if (!Answer) _missingMdxReference("Answer", true); if (!Assessment) _missingMdxReference("Assessment", true); if (!BlockDiagram) _missingMdxReference("BlockDiagram", true); if (!CodeBlock) _missingMdxReference("CodeBlock", true); if (!ComparisonTable) _missingMdxReference("ComparisonTable", true); if (!ContentAttribution) _missingMdxReference("ContentAttribution", true); if (!DefinitionEntry) _missingMdxReference("DefinitionEntry", true); if (!DefinitionGroup) _missingMdxReference("DefinitionGroup", true); if (!English) _missingMdxReference("English", true); if (!Explanation) _missingMdxReference("Explanation", true); if (!FormulaBox) _missingMdxReference("FormulaBox", true); if (!Hinglish) _missingMdxReference("Hinglish", true); if (!ImportantQA) _missingMdxReference("ImportantQA", true); if (!KeyPoints) _missingMdxReference("KeyPoints", true); if (!MCQ) _missingMdxReference("MCQ", true); if (!MermaidDiagram) _missingMdxReference("MermaidDiagram", true); if (!Practical) _missingMdxReference("Practical", true); if (!Prompt) _missingMdxReference("Prompt", true); if (!QAQuestion) _missingMdxReference("QAQuestion", true); if (!SubTopicHeader) _missingMdxReference("SubTopicHeader", true); if (!Theory) _missingMdxReference("Theory", true); if (!TopicOverview) _missingMdxReference("TopicOverview", true); return _jsxs(_Fragment, { children: [_jsxs(Theory, { children: [_jsx(SubTopicHeader, { id: "4.5", title: "Recursive Functions" }), _jsxs(TopicOverview, { title: "Recursive Functions", topicId: "4.5", readingTime: "7 min read", difficulty: "Medium", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["Recursion is one of the most elegant and powerful techniques in programming where a function calls itself to solve a problem. Instead of writing complex loops, you can break a large problem into smaller sub-problems of the same type. Think of it like Russian nesting dolls — each doll contains a smaller version of itself, until you reach the smallest one. In C, every recursive function must have a ", _jsx(_components.strong, { children: "base case" }), " (the smallest problem it can solve directly) and a ", _jsx(_components.strong, { children: "recursive case" }), " (where the function calls itself with a simpler input). This topic covers how recursion works internally using the call stack, how to write recursive functions, and when to use them effectively."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: ["Recursion programming ka sabse elegant aur powerful technique hai jisme ek function khud ko call karta hai problem solve karne ke liye. Complex loops likhne ki jagah tum ek bade problem ko usi type ke chhote sub-problems mein break kar sakte ho. Socho jaise Russian nesting dolls — har doll ke andar uska chhota version hota hai, jab tak sabse chhota doll na mil jaaye. C mein, har recursive function ke paas ek ", _jsx(_components.strong, { children: "base case" }), " hona chahiye (sabse chhoti problem jo directly solve ho sakti hai) aur ek ", _jsx(_components.strong, { children: "recursive case" }), " (jahan function khud ko simpler input ke saath call karta hai). Is topic mein hum dekhenge recursion internally call stack ka use kaise karta hai, recursive functions kaise likhte hain, aur kab effectively use karte hain."] }) })] }), _jsxs(DefinitionGroup, { children: [_jsxs(DefinitionEntry, { term: "Recursion", children: [_jsx(English, { children: _jsx(_components.p, { children: "Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. Each recursive call works on a smaller version of the original problem, progressively moving towards a solution. For example, to calculate 5 factorial, the function calls itself for 4!, then 3!, and so on until it reaches the simplest case of 0! = 1." }) }), _jsx(Hinglish, { children: _jsx(_components.p, { children: "Recursion ek programming technique hai jisme ek function khud ko directly ya indirectly call karta hai problem solve karne ke liye. Har recursive call original problem ke chhote version par kaam karta hai, aur dheere dheere solution ki taraf badhta hai. Jaise, 5 factorial calculate karne ke liye, function khud ko 4! ke liye call karta hai, phir 3! ke liye, aur aise chalta hai jab tak sabse simple case 0! = 1 na aa jaaye." }) })] }), _jsxs(DefinitionEntry, { term: "Base Case", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["A base case is the condition in a recursive function where no further recursive call is made. It acts as the stopping mechanism to prevent infinite recursion. Without a base case, the function would keep calling itself forever, leading to a ", _jsx(_components.strong, { children: "stack overflow" }), " error. For instance, in a factorial function, the base case is when n equals 0 or 1, returning 1 directly."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: ["Base case woh condition hai recursive function mein jahan aur koi recursive call nahi hoti. Yeh ek stopping mechanism ka kaam karti hai jo infinite recursion ko rokti hai. Base case ke bina, function apne aap ko baar baar call karta rahega, jisse ", _jsx(_components.strong, { children: "stack overflow" }), " error aata hai. Jaise, factorial function mein base case yeh hota hai ki jab n equals 0 ya 1 ho, toh seedha 1 return karo."] }) })] }), _jsxs(DefinitionEntry, { term: "Recursive Case", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["The recursive case is the part of the function where it calls itself with a modified (usually smaller) input, moving closer to the base case. Each recursive step should bring the problem one step closer to the base condition. For example, in factorial calculation, the recursive case is ", _jsx(_components.code, { children: "n * factorial(n - 1)" }), ", where the input decreases by 1 each time."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: ["Recursive case woh part hai function ka jisme woh khud ko modified (usually chhote) input ke saath call karta hai, base case ke aur close jaate hue. Har recursive step problem ko base condition ki taraf ek step le jaata hai. Jaise, factorial calculation mein recursive case ", _jsx(_components.code, { children: "n * factorial(n - 1)" }), " hai, jisme input har baar 1 se decrease hota hai."] }) })] }), _jsxs(DefinitionEntry, { term: "Stack Overflow", children: [_jsx(English, { children: _jsx(_components.p, { children: "A stack overflow occurs when the recursive function never reaches its base case, causing it to call itself infinitely. Each function call consumes memory on the system stack, and when the stack runs out of space, the program crashes. This is why every recursive function must have a properly defined base case." }) }), _jsx(Hinglish, { children: _jsx(_components.p, { children: "Stack overflow tab hota hai jab recursive function kabhi apna base case reach nahi karta, jisse woh infinitely khud ko call karta rehta hai. Har function call system stack par memory consume karta hai, aur jab stack ki jagah khatam ho jaati hai, toh program crash ho jaata hai. Isliye har recursive function ka base case properly defined hona chahiye." }) })] }), _jsxs(DefinitionEntry, { term: "Tail Recursion", children: [_jsx(English, { children: _jsx(_components.p, { children: "Tail recursion is a special form of recursion where the recursive call is the very last operation in the function. No computation happens after the recursive call returns. Some compilers can optimize tail-recursive functions into loops, improving performance and preventing stack overflow." }) }), _jsx(Hinglish, { children: _jsx(_components.p, { children: "Tail recursion recursion ka ek special form hai jisme recursive call function mein sabse last operation hota hai. Recursive call ke return hone ke baad koi computation nahi hota. Kuch compilers tail-recursive functions ko loops mein optimize kar sakte hain, jisse performance improve hoti hai aur stack overflow bhi prevent hota hai." }) })] })] }), _jsxs(Explanation, { children: [_jsxs(English, { children: [_jsx(_components.h3, { children: "🔄 How Recursion Works Internally" }), _jsxs(_components.p, { children: ["When a recursive function is called, each call gets its own ", _jsx(_components.strong, { children: "activation record" }), " (also called a stack frame) on the system stack. This record stores the function's parameters, local variables, and the return address. The stack keeps growing with each recursive call until the base case is reached. Once the base case returns a value, the stack starts ", _jsx(_components.strong, { children: "unwinding" }), " — each previous call picks up its pending computation and returns its result to the caller above it."] }), _jsxs(_components.p, { children: ["Let's understand this with the classic example of ", _jsx(_components.strong, { children: "factorial calculation" }), ":"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "🔄 Recursion Internally Kaise Kaam Karta Hai" }), _jsxs(_components.p, { children: ["Jab ek recursive function call hota hai, har call ko system stack par apna ek ", _jsx(_components.strong, { children: "activation record" }), " (jise stack frame bhi kehte hain) milta hai. Is record mein function ke parameters, local variables, aur return address store hota hai. Har recursive call ke saath stack badhta rehta hai jab tak base case na reach ho jaaye. Jab base case ek value return karta hai, tab stack ", _jsx(_components.strong, { children: "unwind" }), " hona shuru karta hai — har previous call apna pending computation leta hai aur apna result caller ko return karta hai."] }), _jsxs(_components.p, { children: ["Chalo isko ", _jsx(_components.strong, { children: "factorial calculation" }), " ke classic example se samajhte hain:"] })] }), _jsx(CodeBlock, { language: "c", children: `#include int factorial(int n) { if (n 0 || n 1) { // Base case return 1; } return n * factorial(n - 1); // Recursive case } int main() { int num = 5; printf("Factorial of %d = %d\\n", num, factorial(num)); return 0; }` }), _jsxs(English, { children: [_jsx(_components.p, { children: _jsx(_components.strong, { children: "Output:" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "Factorial of 5 = 120\n" }) }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Trace of how the calls unfold:" }) }), _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "left" }, children: "Call" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Expression" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Waiting For" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(5)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "5 * factorial(4)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: ["Result of ", _jsx(_components.code, { children: "factorial(4)" })] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(4)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "4 * factorial(3)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: ["Result of ", _jsx(_components.code, { children: "factorial(3)" })] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(3)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "3 * factorial(2)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: ["Result of ", _jsx(_components.code, { children: "factorial(2)" })] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(2)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "2 * factorial(1)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: ["Result of ", _jsx(_components.code, { children: "factorial(1)" })] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(1)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "return 1" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Base case reached!" })] })] })] }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Unwinding phase (stack pops):" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(1)" }), " returns ", _jsx(_components.code, { children: "1" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(2)" }), " computes ", _jsx(_components.code, { children: "2 * 1 = 2" }), ", returns ", _jsx(_components.code, { children: "2" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(3)" }), " computes ", _jsx(_components.code, { children: "3 * 2 = 6" }), ", returns ", _jsx(_components.code, { children: "6" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(4)" }), " computes ", _jsx(_components.code, { children: "4 * 6 = 24" }), ", returns ", _jsx(_components.code, { children: "24" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(5)" }), " computes ", _jsx(_components.code, { children: "5 * 24 = 120" }), ", returns ", _jsx(_components.code, { children: "120" })] }), "\n"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.p, { children: _jsx(_components.strong, { children: "Output:" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "Factorial of 5 = 120\n" }) }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Calls kaise unfold hote hain — trace:" }) }), _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "left" }, children: "Call" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Expression" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Kiska Wait Hai" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(5)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "5 * factorial(4)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: [_jsx(_components.code, { children: "factorial(4)" }), " ka result"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(4)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "4 * factorial(3)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: [_jsx(_components.code, { children: "factorial(3)" }), " ka result"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(3)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "3 * factorial(2)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: [_jsx(_components.code, { children: "factorial(2)" }), " ka result"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(2)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "2 * factorial(1)" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: [_jsx(_components.code, { children: "factorial(1)" }), " ka result"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "factorial(1)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "return 1" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Base case mil gaya!" })] })] })] }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Unwinding phase (stack se values pop hote hain):" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(1)" }), " returns ", _jsx(_components.code, { children: "1" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(2)" }), " calculate karta hai ", _jsx(_components.code, { children: "2 * 1 = 2" }), ", returns ", _jsx(_components.code, { children: "2" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(3)" }), " calculate karta hai ", _jsx(_components.code, { children: "3 * 2 = 6" }), ", returns ", _jsx(_components.code, { children: "6" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(4)" }), " calculate karta hai ", _jsx(_components.code, { children: "4 * 6 = 24" }), ", returns ", _jsx(_components.code, { children: "24" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "factorial(5)" }), " calculate karta hai ", _jsx(_components.code, { children: "5 * 24 = 120" }), ", returns ", _jsx(_components.code, { children: "120" })] }), "\n"] })] }), _jsx(BlockDiagram, { title: "Recursion Call Stack Visualization", children: _jsx(_components.pre, { children: _jsx(_components.code, { children: " CALL STACK (growing downward)\r\n ┌──────────────────────┐\r\n │ factorial(5) │ ← Waiting for factorial(4)\r\n ├──────────────────────┤\r\n │ factorial(4) │ ← Waiting for factorial(3)\r\n ├──────────────────────┤\r\n │ factorial(3) │ ← Waiting for factorial(2)\r\n ├──────────────────────┤\r\n │ factorial(2) │ ← Waiting for factorial(1)\r\n ├──────────────────────┤\r\n │ factorial(1) │ ← BASE CASE! Returns 1\r\n └──────────────────────┘\r\n\r\n UNWINDING (popping upward)\r\n factorial(1) → 1\r\n factorial(2) → 2 × 1 = 2\r\n factorial(3) → 3 × 2 = 6\r\n factorial(4) → 4 × 6 = 24\r\n factorial(5) → 5 × 24 = 120 ← FINAL RESULT\n" }) }) }), _jsxs(English, { children: [_jsx(_components.h3, { children: "📌 Fibonacci Series Using Recursion" }), _jsxs(_components.p, { children: ["Another classic example is computing the ", _jsx(_components.strong, { children: "Fibonacci series" }), ", where each number is the sum of the two preceding numbers: 0, 1, 1, 2, 3, 5, 8, 13, ..."] }), _jsx(_components.p, { children: "The recursive formula is:" }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "fib(0) = 0" }), " (base case)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "fib(1) = 1" }), " (base case)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "fib(n) = fib(n-1) + fib(n-2)" }), " for ", _jsx(_components.code, { children: "n > 1" }), " (recursive case)"] }), "\n"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "📌 Recursion Se Fibonacci Series Banana" }), _jsxs(_components.p, { children: ["Doosra classic example hai ", _jsx(_components.strong, { children: "Fibonacci series" }), " compute karna, jisme har number do preceding numbers ka sum hota hai: 0, 1, 1, 2, 3, 5, 8, 13, ..."] }), _jsx(_components.p, { children: "Recursive formula yeh hai:" }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "fib(0) = 0" }), " (base case)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "fib(1) = 1" }), " (base case)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "fib(n) = fib(n-1) + fib(n-2)" }), " jab ", _jsx(_components.code, { children: "n > 1" }), " (recursive case)"] }), "\n"] })] }), _jsx(CodeBlock, { language: "c", children: `#include int fibonacci(int n) { if (n == 0) return 0; // Base case 1 if (n == 1) return 1; // Base case 2 return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case } int main() { int i, n = 8; printf("Fibonacci Series (first %d terms):\\n", n); for (i = 0; i < n; i++) { printf("%d ", fibonacci(i)); } printf("\\n"); return 0; }` }), _jsxs(English, { children: [_jsx(_components.p, { children: _jsx(_components.strong, { children: "Output:" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "Fibonacci Series (first 8 terms):\r\n0 1 1 2 3 5 8 13\n" }) }), _jsxs(_components.p, { children: ["Notice how ", _jsx(_components.code, { children: "fibonacci(5)" }), " creates a tree of calls:"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.p, { children: _jsx(_components.strong, { children: "Output:" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "Fibonacci Series (first 8 terms):\r\n0 1 1 2 3 5 8 13\n" }) }), _jsxs(_components.p, { children: ["Dekho kaise ", _jsx(_components.code, { children: "fibonacci(5)" }), " ek call tree create karta hai:"] })] }), _jsx(MermaidDiagram, { children: _jsx(_components.pre, { children: _jsx(_components.code, { className: "language-mermaid", children: "flowchart TD\r\n A[\"fib(5)\"] --> B[\"fib(4)\"]\r\n A --> C[\"fib(3)\"]\r\n B --> D[\"fib(3)\"]\r\n B --> E[\"fib(2)\"]\r\n C --> F[\"fib(2)\"]\r\n C --> G[\"fib(1)=1\"]\r\n D --> H[\"fib(2)\"]\r\n D --> I[\"fib(1)=1\"]\r\n E --> J[\"fib(1)=1\"]\r\n E --> K[\"fib(0)=0\"]\r\n F --> L[\"fib(1)=1\"]\r\n F --> M[\"fib(0)=0\"]\r\n H --> N[\"fib(1)=1\"]\r\n H --> O[\"fib(0)=0\"]\n" }) }) }), _jsxs(English, { children: [_jsx(_components.h3, { children: "⚠️ Common Pitfalls in Recursion" }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Missing Base Case:" }), " If you forget the base case, the function calls itself infinitely, causing a stack overflow crash."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Wrong Base Case:" }), " Even if a base case exists, it might not be reachable for certain inputs, leading to infinite recursion."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Redundant Calls (Overlapping Subproblems):" }), " In the Fibonacci example above, ", _jsx(_components.code, { children: "fib(3)" }), " is computed twice, ", _jsx(_components.code, { children: "fib(2)" }), " is computed three times. This leads to exponential time complexity ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.6644em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), ". This can be optimized using ", _jsx(_components.strong, { children: "memoization" }), " (storing previously computed results)."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Not Progressing Toward Base Case:" }), " If each recursive call doesn't move closer to the base case (e.g., calling ", _jsx(_components.code, { children: "factorial(n)" }), " instead of ", _jsx(_components.code, { children: "factorial(n-1)" }), "), the function will recurse infinitely."] }), "\n"] }), _jsx(_components.p, { children: "Let's look at a safe recursive pattern:" })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "⚠️ Recursion Mein Common Galtiyan" }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Base Case Missing:" }), " Agar base case bhool jaao, toh function infinitely khud ko call karta rahega, jisse stack overflow crash hoga."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Galat Base Case:" }), " Base case exist karta bhi ho, agar certain inputs ke liye reachable nahi hai, toh bhi infinite recursion ho jayega."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Redundant Calls (Overlapping Subproblems):" }), " Upar ke Fibonacci example mein, ", _jsx(_components.code, { children: "fib(3)" }), " do baar compute ho raha hai, ", _jsx(_components.code, { children: "fib(2)" }), " teen baar. Isse exponential time complexity ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.6644em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " aati hai. Isko ", _jsx(_components.strong, { children: "memoization" }), " (pehle se computed results store karna) se optimize kar sakte hain."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Base Case Ki Taraf Progress Na Hona:" }), " Agar har recursive call base case ki taraf move nahi kar raha (jaise ", _jsx(_components.code, { children: "factorial(n)" }), " call karna ", _jsx(_components.code, { children: "factorial(n-1)" }), " ki jagah), toh function infinitely recurse karega."] }), "\n"] }), _jsx(_components.p, { children: "Chalo ek safe recursive pattern dekhte hain:" })] }), _jsx(CodeBlock, { language: "c", children: `#include // Safe recursive pattern: always check base case FIRST, // then make recursive call with PROGRESS toward base case int power(int base, int exp) { // Base case if (exp == 0) return 1; // Recursive case with progress (exp decreases each time) return base * power(base, exp - 1); } int main() { printf("2^10 = %d\\n", power(2, 10)); return 0; }` }), _jsxs(English, { children: [_jsx(_components.p, { children: _jsx(_components.strong, { children: "Output:" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "2^10 = 1024\n" }) }), _jsx(_components.h3, { children: "📊 Recursion vs Iteration Comparison" }), _jsx(_components.p, { children: "Both recursion and iteration can solve the same problems, but they differ in approach and performance characteristics:" })] }), _jsxs(Hinglish, { children: [_jsx(_components.p, { children: _jsx(_components.strong, { children: "Output:" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "2^10 = 1024\n" }) }), _jsx(_components.h3, { children: "📊 Recursion vs Iteration Ka Comparison" }), _jsx(_components.p, { children: "Recursion aur iteration dono same problems solve kar sakte hain, lekin approach aur performance characteristics mein farak hota hai:" })] }), _jsx(ComparisonTable, { title: "Recursion vs Iteration", children: _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "left" }, children: "Feature" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Recursion" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Iteration" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Mechanism" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Function calls itself" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Uses loops (for, while)" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Memory" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "More memory (stack frames for each call)" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Less memory (no extra stack usage)" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Speed" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Slower due to function call overhead" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Generally faster" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Code readability" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Often cleaner for problems like tree traversal" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Can become complex for nested logic" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Stack overflow risk" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Yes, if base case is missing" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "No such risk" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Best for" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Tree/graph traversal, divide-and-conquer, backtracking" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Simple repetitive tasks, counting, accumulation" })] })] })] }) }), _jsxs(FormulaBox, { title: "Time Complexity of Recursive Functions", children: [_jsx(_components.p, { children: _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "⇒" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mord text", children: _jsx(_components.span, { className: "mord", children: " for factorial" }) })] })] }) }) }), _jsx(_components.p, { children: _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "⇒" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.6644em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mord text", children: _jsx(_components.span, { className: "mord", children: " for naive Fibonacci" }) })] })] }) }) })] }), _jsxs(Analogy, { children: [_jsx(English, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "The Russian Doll Analogy:" }), " Imagine you have a set of 5 Russian nesting dolls. To find the smallest doll inside, you open the outermost doll (problem of size 5), which reveals a slightly smaller doll (problem of size 4). You open that one too, and keep going — this is like the recursive calls building up. When you finally reach the smallest solid doll (base case — problem of size 1), you can't open it further. Now you start closing them back up (unwinding phase), and each doll gets its answer from the one inside it."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Russian Doll Analogy:" }), " Socho tumhare paas 5 Russian nesting dolls ka set hai. Sabse chhota doll dhoondne ke liye tum sabse bahar ka doll kholte ho (problem of size 5), jiske andar thoda chhota doll milta hai (problem of size 4). Tum usse bhi kholte ho, aur aise karte jao — yeh recursive calls build up hone jaisa hai. Jab finally sabse chhota solid doll mil jaata hai (base case — problem of size 1), toh tum aur nahi khol sakte. Ab tum unhe band karna shuru karte ho (unwinding phase), aur har doll apne andar wale doll se answer leta hai."] }) })] }), _jsx(KeyPoints, { children: _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["Every recursive function ", _jsx(_components.strong, { children: "must" }), " have a ", _jsx(_components.strong, { children: "base case" }), " to stop recursion; without it, stack overflow occurs."] }), "\n", _jsxs(_components.li, { children: ["Each recursive call creates a new ", _jsx(_components.strong, { children: "activation record" }), " (stack frame) on the system stack."] }), "\n", _jsxs(_components.li, { children: ["Recursion is ideal for problems with a ", _jsx(_components.strong, { children: "divide-and-conquer" }), " nature like tree traversal, factorial, Fibonacci, Tower of Hanoi, and sorting (merge sort, quick sort)."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Tail recursion" }), " (where recursive call is the last operation) can be optimized by some compilers to avoid extra stack usage."] }), "\n", _jsxs(_components.li, { children: ["Naive recursion can lead to ", _jsx(_components.strong, { children: "overlapping subproblems" }), " — use ", _jsx(_components.strong, { children: "memoization" }), " to store results and avoid redundant computation."] }), "\n", _jsxs(_components.li, { children: ["Always ensure the recursive call ", _jsx(_components.strong, { children: "progresses toward the base case" }), " to prevent infinite recursion."] }), "\n"] }) })] })] }), "\n", _jsx(Practical, { children: _jsxs(ImportantQA, { children: [_jsxs(QAQuestion, { marks: 2, children: [_jsx(Prompt, { children: "Define recursion in the context of C functions and give one simple example of a recursive function." }), _jsx(Answer, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Recursion" }), " means kisi function ko uske andar hi call karna hai — yaani, function apne aap ko call karta hai. Is process mein function ek ", _jsx(_components.strong, { children: "base case" }), " define karta hai, jo recursion ko rokta hai. ", _jsx(_components.strong, { children: "Example:" }), " ", _jsx(_components.code, { children: "factorial(5)" }), " function apne aap ko ", _jsx(_components.code, { children: "5 * factorial(4)" }), " ki tarah call karta hai, jab tak base case ", _jsx(_components.code, { children: "factorial(0) == 1" }), " na mil jaaye. Har recursive function mein ek ", _jsx(_components.strong, { children: "base case" }), " hona zaroori hai, warna recursion ", _jsx(_components.strong, { children: "infinite loop" }), " ban jayega aur stack overflow error aayega!"] }) })] }), _jsxs(QAQuestion, { marks: 4, children: [_jsx(Prompt, { children: "Explain the working of recursion with a flowchart-like structure, and mention at least two advantages of using recursion." }), _jsx(Answer, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Recursion ka kaam yeh hai:" }), " 1. ", _jsx(_components.strong, { children: "Function Call:" }), " Function khud ko call karta hai with a ", _jsx(_components.strong, { children: "smaller input" }), ". 2. ", _jsx(_components.strong, { children: "Base Case Check:" }), " Agar base case mil jaaye, toh recursion ruk jaata hai aur value return hoti hai. 3. ", _jsx(_components.strong, { children: "Recursive Case:" }), " Agar base case nahi mila, toh function apne aap ko dubara call karta hai. 4. ", _jsx(_components.strong, { children: "Stack Unwinding:" }), " Jab base case milta hai, har recursive call return hota hai aur kaam hota hai. ", _jsx(_components.strong, { children: "Advantages:" }), " - ", _jsx(_components.strong, { children: "Code Simple & Clean:" }), " Complex problems (jaise tree traversal, Fibonacci series) recursion se zyada readable ban jaate hain. - ", _jsx(_components.strong, { children: "Divide and Conquer:" }), " Recursion naturally ", _jsx(_components.strong, { children: "divide and conquer" }), " strategy follow karta hai, jaise merge sort mein. Recursion ka disadvantage yeh hai ki har call ke liye ", _jsx(_components.strong, { children: "stack memory" }), " use hoti hai, bahut deep recursion se ", _jsx(_components.strong, { children: "stack overflow" }), " ho sakta hai."] }) })] }), _jsxs(QAQuestion, { marks: 6, children: [_jsx(Prompt, { children: "Write a complete C program to compute the factorial of a number using recursion, and explain each step of its execution for input n = 4." }), _jsx(Answer, { children: _jsxs(_components.p, { children: ["Yeh program recursion use karke factorial calculate karta hai: ", _jsx(_components.code, { children: "c #include // Recursive function for factorial int factorial(int n) { // Base case: factorial of 0 or 1 is 1 if (n 0 || n 1) { return 1; } // Recursive case: n * factorial(n-1) else { return n * factorial(n - 1); } } int main() { int num = 4; printf("Factorial of %d is %d\\n", num, factorial(num)); return 0; } " }), " ", _jsx(_components.strong, { children: "Output:" }), " ", _jsx(_components.code, { children: "Factorial of 4 is 24" }), " ", _jsxs(_components.strong, { children: ["Execution Steps for ", _jsx(_components.code, { children: "factorial(4)" }), ":"] }), " 1. ", _jsx(_components.strong, { children: "First call:" }), " ", _jsx(_components.code, { children: "factorial(4)" }), " → ", _jsx(_components.code, { children: "4 != 0" }), " so else block executes, returns ", _jsx(_components.code, { children: "4 * factorial(3)" }), " 2. ", _jsx(_components.strong, { children: "Second call:" }), " ", _jsx(_components.code, { children: "factorial(3)" }), " → returns ", _jsx(_components.code, { children: "3 * factorial(2)" }), " 3. ", _jsx(_components.strong, { children: "Third call:" }), " ", _jsx(_components.code, { children: "factorial(2)" }), " → returns ", _jsx(_components.code, { children: "2 * factorial(1)" }), " 4. ", _jsx(_components.strong, { children: "Fourth call:" }), " ", _jsx(_components.code, { children: "factorial(1)" }), " → base case mil gaya! returns ", _jsx(_components.code, { children: "1" }), " 5. ", _jsx(_components.strong, { children: "Stack Unwinding:" }), " - ", _jsx(_components.code, { children: "factorial(2)" }), " becomes ", _jsx(_components.code, { children: "2 * 1 = 2" }), " - ", _jsx(_components.code, { children: "factorial(3)" }), " becomes ", _jsx(_components.code, { children: "3 * 2 = 6" }), " - ", _jsx(_components.code, { children: "factorial(4)" }), " becomes ", _jsx(_components.code, { children: "4 * 6 = 24" }), " 6. Final result ", _jsx(_components.code, { children: "24" }), " print hota hai. Har recursive call ke liye ", _jsx(_components.strong, { children: "stack frame" }), " create hota hai jo local variables aur return address store karta hai. Isliye recursion ka ", _jsx(_components.strong, { children: "time complexity" }), " same hota hai, but ", _jsx(_components.strong, { children: "space complexity" }), " iteration se zyada hoti hai."] }) })] })] }) }), "\n", _jsxs(Assessment, { topicId: "4.5", children: [_jsx(MCQ, { questions: [{ "id": "b8e49e7d-dea7-494a-9ed6-aa926098bd8d", "q": "What is recursion in C programming?", "options": ["A loop that runs indefinitely until a condition is met", "A function that calls itself directly or indirectly", "A function that is called from the main function", "A function that returns multiple values"], "answer": 1, "hint": "Think about the function that calls itself.", "explanation": "Recursion in C is a programming technique where a function calls itself directly or indirectly to solve a problem by breaking it down into smaller, similar sub-problems." }, { "id": "9b7a866c-0084-4f8c-8aee-dea4655e5705", "q": "What is a potential consequence of a recursive function without a base case?", "options": ["Compiler error", "Faster execution", "Infinite recursion and stack overflow", "Memory leak"], "answer": 2, "hint": "Consider what happens when a function has no condition to stop calling itself.", "explanation": "A recursive function must have a base case to stop the recursion; otherwise, it will call itself infinitely until the system runs out of stack memory, leading to a stack overflow error." }, { "id": "4f2e0b4f-6cee-43a1-8be9-1ccee0da1827", "q": "How does recursion typically affect memory usage compared to an iterative approach?", "options": ["It uses less memory", "It uses the same amount of memory", "It eliminates the need for local variables", "It uses more memory due to the call stack"], "answer": 3, "hint": "Think about how recursion uses memory during execution.", "explanation": "Each recursive call adds a new activation record (stack frame) to the call stack to store local variables and return address. This consumes additional memory compared to iteration, which uses constant memory." }, { "id": "290d3356-e1bc-485e-9b0c-7050fb9e9d05", "q": "Which of the following is the correct base case for a recursive factorial function?", "options": ["if (n 0) return 1;", "if (n 0) return 0;", "if (n == 1) return n;", "if (n > 1) return 1;"], "answer": 0, "hint": "Consider the factorial formula: n! = n * (n-1)!. What is the simplest case?", "explanation": "The base case for factorial is when n equals 0 or 1, because 0! and 1! are defined as 1. The recursive step then multiplies n by the factorial of n-1." }, { "id": "b1e9b13f-d23c-416f-a487-9647767f428a", "q": "How many times will the recursive function `fact` be called for `fact(4)` if defined as `int fact(int n) { if (n==0) return 1; else return n*fact(n-1); }`?", "options": ["4 times", "5 times", "3 times", "6 times"], "answer": 1, "hint": "Write out the recursive calls for factorial(4) to see the pattern.", "explanation": "The function will make 5 calls: factorial(4), factorial(3), factorial(2), factorial(1), and factorial(0). Each call before the base case waits for the result of the next call." }, { "id": "7dd26737-2487-48d3-a1d5-ff2e0b094d7a", "q": "What does the following recursive function compute?`int func(int n) {`` if (n <= 0) return 1;`` else return n * func(n-1);``}`", "options": ["Sum of numbers from 1 to n", "nth Fibonacci number", "n factorial (n!)", "Power of 2 raised to n"], "answer": 2, "hint": "Look at the `return` statement inside the function. It calls itself before returning a value.", "explanation": "This is a standard recursive function. For any positive integer n, it computes the product of n and (n-1) until the base case n=0 returns 1, effectively calculating n factorial." }, { "id": "220d7f2c-7308-4015-87b5-43d346558808", "q": "What is the output of the following code for `fib(3)`?`int fib(int n) {`` if (n <= 1) return n;`` else return fib(n-1) + fib(n-2);``}`", "options": ["2", "3", "1", "4"], "answer": 0, "hint": "Trace the function with small input like n=3. What are the intermediate returns?", "explanation": "For fib(3): fib(3) calls fib(2) and fib(1); fib(2) calls fib(1) and fib(0). fib(0) returns 0, fib(1) returns 1, so fib(2) returns 1, then fib(3) returns 1+1=2. This demonstrates the exponential call growth without memoization." }, { "id": "3510b508-890b-40ff-b3ef-169293f6bb41", "q": "Which of the following best describes a tail-recursive function?", "options": ["A function that calls multiple other functions recursively", "A function with no base case", "A function that returns multiple values from a recursive call", "A function where the recursive call is the last operation performed"], "answer": 3, "hint": "Tail recursion means the recursive call is the last action in the function.", "explanation": "A function is tail recursive if the recursive call is the final operation, meaning no computation is performed after the call returns. This allows some compilers to optimize the recursion into a loop, avoiding stack growth." }, { "id": "af6dfee6-d84c-48dd-ab0b-710d0a6c58c8", "q": "Why does recursion often lead to higher memory consumption than iteration?", "options": ["Recursive functions are always compiled to less efficient code", "Each call creates a new stack frame, consuming additional memory", "Recursion requires storing the entire program state", "Iterative loops use more memory to manage loop counters"], "answer": 1, "hint": "Remember that each recursive call uses a new stack frame.", "explanation": "Each recursive call creates a new activation record on the stack, storing parameters, local variables, and the return address. This leads to higher memory consumption than an iterative loop, which reuses the same memory space." }, { "id": "25229fe6-93d2-4431-bbf1-597871311a74", "q": "Which statement about recursion vs. iteration is generally true?", "options": ["Recursion is always slower and less efficient than iteration", "Iteration cannot solve problems that recursion can", "Recursion can provide simpler, more readable solutions for certain problems", "Recursion uses less memory than iteration for all problems"], "answer": 2, "hint": "Consider that recursion can make code simpler for problems that are naturally recursive, like tree traversal.", "explanation": "Recursion is not always slower; for some problems like tree traversals or divide-and-conquer algorithms, it can be both elegant and efficient. However, for simple linear problems, iteration may be faster due to less function call overhead." }], topicId: "4.5" }), _jsx(ContentAttribution, { sourceTitle: "Curriculum Reference", sourceUrl: "https://learningway.in", professor: "Faculty Review Team", model: "Curriculum AI", seoTitle: "Recursive functions", seoDesc: "Master Recursive functions with comprehensive notes, real-world examples, and practice quiz on LearningWay.", seoKeywords: "recursive functions, recursive functions notes, recursive functions examples, diploma engineering notes, practice quiz, learningway" })] })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent }; function _missingMdxReference(id, component) { throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it."); }