Scribd
Upload
21 views6 pages

Notes 4 Recursion

Recursion in C is a method where a function calls itself to solve problems by breaking them into smaller subproblems, continuing until a base condition is met. Key examples include calculating factorials, binomial coefficients, Fibonacci series, and finding the greatest common divisor (GCD). Each recursive call creates a new stack frame, and excessive recursion can lead to stack overflow.

Uploaded by

garvita4321
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
21 views6 pages

Notes 4 Recursion

Recursion in C is a method where a function calls itself to solve problems by breaking them into smaller subproblems, continuing until a base condition is met. Key examples include calculating factorials, binomial coefficients, Fibonacci series, and finding the greatest common divisor (GCD). Each recursive call creates a new stack frame, and excessive recursion can lead to stack overflow.

Uploaded by

garvita4321
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

RECURSION

Basic Definition (Beginner Level)

Recursion in C is when a function calls itself


directly or indirectly to solve a problem.
It continues calling itself with smaller inputs
until it reaches a base condition, which stops
the recursion.

🔹 Example:

int factorial(int n) {
if (n == 0) return 1; // base case
return n * factorial(n-1); // recursive call
}

---
Intermediate Definition (With Control Flow
Understanding)

In C, recursion is a technique where a function


solves a larger problem by breaking it into
smaller subproblems of the same type, solved
by recursive calls.
Each recursive call creates a new stack frame
in memory with its own parameters and local
variables.
A base case is crucial to avoid infinite
recursion and stack overflow.

🔹 Example Insight: In the factorial function


above, the recursive calls build up a call stack
like:

factorial(4) → factorial(3) → factorial(2) →


factorial(1) → factorial(0)
Then results return back in reverse order as
the stack unwinds.

---

Advanced Definition (With Memory and


Performance Considerations)

In C, recursion involves a function invoking


itself with new arguments, leading to a last-in-
first-out (LIFO) series of function calls
managed via the call stack.
Each recursive call consumes stack memory,
and excessive recursion can cause a stack
overflow.
Here are three classic examples of
recursion in C using:

1. Binomial Coefficient
2. Fibonacci Series

3. Greatest Common Divisor (GCD)

---

1️⃣ Binomial Coefficient (nCr = n! / (r! *


(n-r)!))

int binomialCoeff(int n, int r) {


if (r == 0 || r == n) return 1; // base
cases
return binomialCoeff(n - 1, r - 1) +
binomialCoeff(n - 1, r);
}

🔹 Example:
binomialCoeff(5, 2) returns 10

---

2️⃣ Fibonacci Series

int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n -
2);
}
🔹 Example:
fibonacci(6) returns 8
(Since: 0, 1, 1, 2, 3, 5, 8)

---

3️⃣ Greatest Common Divisor (GCD) using


Euclidean Algorithm

int gcd(int a, int b) {


if (b == 0) return a;
return gcd(b, a % b);
}

🔹 Example:
gcd(24, 18) returns 6

You might also like