C Programming • Arrays & Functions
C Programming / Recursion

Recursion

Notes 3 Arrays & Functions
Quick concept

Recursion is a process in which a function calls itself to solve a problem by breaking it into smaller versions of the same problem.

Notes

Recursion

Recursion is a process in which a function calls itself to solve a problem by breaking it into smaller versions of the same problem.

💡 Example

A function factorial() can call itself to calculate the factorial of a smaller number.

How Recursion Works

A recursive function normally has two important parts: a base case and a recursive case.

1. Base Case

The base case is the condition that stops the recursive calls. Without a proper base case, recursion can continue indefinitely.

💡 Example

In factorial, factorial(0) = 1 can be used as the base case.

2. Recursive Case

The recursive case is the part of the function where the function calls itself with a smaller or simpler value.

💡 Example

factorial(n) = n * factorial(n - 1)

Simple Example of Recursion

#include <stdio.h> int countDown(int n) { if (n == 0) return 0; // base case printf("%d ", n); return countDown(n - 1); // recursive call } int main() { countDown(5); return 0; }

Expected Output

5 4 3 2 1

Real-World Idea

Recursion can be understood like solving a large task by repeatedly solving a smaller version of the same task until a simple stopping condition is reached.

🌍 Example

A folder can contain subfolders, and each subfolder can contain more subfolders. A program can process them using the same logic repeatedly.

Practical Example

Problem Statement

Write a C program to find the factorial of a positive integer using recursion.

Learning Outcomes

  • Understand the concept of recursive function calls.
  • Identify the base case and recursive case.
  • Use recursion to calculate factorial.

Hint

Define a function factorial() that returns 1 when n == 0. Otherwise return n * factorial(n - 1).

Theory

Factorial of a non-negative integer n is the product of all positive integers from 1 to n. Recursion calculates it by repeatedly reducing the value of n until the base case is reached.

💡 Example

5! = 5 × 4 × 3 × 2 × 1 = 120

Program

#include <stdio.h> int factorial(int n) { if (n == 0) return 1; // base case return n * factorial(n - 1); // recursive call } int main() { int n, result; printf("Enter a positive integer: "); scanf("%d", &n); // calculate factorial using recursion result = factorial(n); printf("Factorial of %d = %d ", n, result); return 0; }

Expected Output

Enter a positive integer: 5

Factorial of 5 = 120

Working of the Example

factorial(5) ↓ 5 × factorial(4) ↓ 5 × 4 × factorial(3) ↓ 5 × 4 × 3 × factorial(2) ↓ 5 × 4 × 3 × 2 × factorial(1) ↓ 5 × 4 × 3 × 2 × 1 ↓ 120

Note

Every recursive function must have a proper stopping condition. The base case prevents the function from calling itself forever.

Advantages of Recursion

Recursion can make some problems easier to express when the problem naturally consists of smaller versions of itself.

💡 Example

Problems involving factorial, Fibonacci series, tree structures and divide-and-conquer techniques can be expressed using recursion.

Disadvantages of Recursion

Recursion can use additional memory because each function call remains active until the recursive calls return. Poorly designed recursion can also lead to excessive calls.

💡 Example

A recursive function without a correct base case may continue calling itself until the program runs out of available stack space.

Recursion vs Iteration

Recursion Iteration
Function calls itself. Uses loops such as for or while.
Requires a base case. Requires a loop condition.
Uses function-call stack memory. Usually uses less additional stack memory.

Quick Revision

Term Remember
Recursion A function calling itself.
Base Case Stops the recursive calls.
Recursive Case Makes the function call itself again.
Factorial A common example of recursion.

Important Exam Questions

Short Answer Questions

  1. What is recursion?
  2. What is a recursive function?
  3. What is a base case?
  4. What is a recursive case?
  5. Why is a base case necessary in recursion?
  6. Give one example of a problem that can be solved using recursion.

Long Answer Questions

  1. Explain recursion in C with a suitable example.
  2. Explain base case and recursive case with an example.
  3. Write a C program to calculate factorial using recursion.
  4. Differentiate between recursion and iteration.
🎥 Recommended Learning

Watch a beginner-friendly explanation of recursion and recursive functions in C.

▶ Watch: Recursion in C — Hindi

📝 Handwritten Notes

A short handwritten-style revision sheet for recursion will be provided here.

🧠 Mind Map

Use the mind map for quick revision of recursive call, base case and recursive case.