Mada za sehemu hiiImplementing functionsMada 2
- Implementing user-defined functions and function calls in a program
- Implementing recursive function in a program
Recursive Functions in Programming

A recursive function is a function that calls itself to solve a problem. This technique is called recursion. Instead of using loops (like for or while), a recursive function breaks down a large problem into smaller parts by calling itself repeatedly until it reaches a simple case that it can solve directly.
Think of it like looking into two mirrors facing each other — you see infinite reflections of yourself. The function keeps calling itself again and again, creating a "chain" of calls.
Every recursive function has two essential parts:
-
Base Case — A simple condition that stops the recursion. When the base case is true, the function returns a value without calling itself again. Without a base case, the function would call itself forever (infinite loop).
-
Recursive Case (Recursive Call) — The part where the function calls itself with a smaller or simpler version of the problem.
The recursion continues until the base case is reached.
void recurse() { // Function declaration
// ... some code ...
recurse(); // Function calls itself
// ... some code ...
}
int main() {
recurse(); // Initial function call
return 0;
}
The general structure:
returnType functionName(parameters) {
if (baseCaseCondition) {
return simpleValue; // Base case - stop recursion
} else {
return functionName(smallerProblem); // Recursive call
}
}
Problem: Write a program to compute the factorial of a number using recursion.
Factorial of n (written as n!) = 1 × 2 × 3 × ... × n For example: 5! = 1 × 2 × 3 × 4 × 5 = 120
Solution:
#include <iostream>
using namespace std;
int factorial(int n);
int main() {
int n, result;
cout << "Enter a non-negative number: ";
cin >> n;
result = factorial(n);
cout << "Factorial of " << n << " = " << result;
return 0;
}
int factorial(int n) {
// Base case: if n is 1 or 0, return 1
if (n <= 1) {
return 1;
} else {
// Recursive case: n! = n × (n-1)!
return n * factorial(n - 1);
}
}
How it works for n = 4:
- factorial(4) = 4 × factorial(3)
- factorial(3) = 3 × factorial(2)
- factorial(2) = 2 × factorial(1)
- factorial(1) = 1 (base case)
Now we unwind: 1 × 2 = 2, then 2 × 3 = 6, then 6 × 4 = 24
Output:
Enter a non-negative number: 4
Factorial of 4 = 24
Problem: Write a program to find the sum of all integers from 1 to n using recursion.
Solution:
#include <iostream>
using namespace std;
int add(int n);
int main() {
int n;
cout << "Enter a positive integer: ";
cin >> n;
cout << "Sum = " << add(n);
return 0;
}
int add(int n) {
// Base case: when n becomes 0, return 0
if (n != 0) {
return n + add(n - 1); // Recursive call
} else {
return 0;
}
}
How it works for n = 5:
- add(5) = 5 + add(4)
- add(4) = 4 + add(3)
- add(3) = 3 + add(2)
- add(2) = 2 + add(1)
- add(1) = 1 + add(0)
- add(0) = 0 (base case)
Unwinding: 0 + 1 = 1, then 1 + 2 = 3, then 3 + 3 = 6, then 6 + 4 = 10, then 10 + 5 = 15
Problem: Write a program to print the Fibonacci series using recursion.
In the Fibonacci series, each number is the sum of its previous two numbers: 0, 1, 1, 2, 3, 5, 8, 13, ...
Solution:
#include <iostream>
using namespace std;
int fib(int x) {
// Base case: fib(0) = 0, fib(1) = 1
if (x == 0 || x == 1) {
return x;
} else {
// Recursive case: fib(n) = fib(n-1) + fib(n-2)
return fib(x - 1) + fib(x - 2);
}
}
int main() {
int x, i = 0;
cout << "Enter the number of terms of series: ";
cin >> x;
cout << "Fibonacci Series: ";
while (i < x) {
cout << " " << fib(i);
i++;
}
return 0;
}
Output:
Enter the number of terms of series: 7
Fibonacci Series: 0 1 1 2 3 5 8
Recursion offers several benefits:
- Shorter and clearer code — Complex problems can be solved with fewer lines of code
- Solves inherently recursive problems — Problems like tree traversals, factorials, and Fibonacci sequences are naturally suited for recursion
- Reduces coding time — Less code to write compared to loops
- Always define a base case to stop recursion
- The recursive call must move toward the base case (the problem gets smaller each time)
- Without a base case, the program will run forever (infinite recursion) and crash
- Recursion can be slower than loops because of the overhead of function calls
In Tanzania, recursive functions are used in mobile banking applications. For example, when calculating how much airtime credit you can buy with a given amount of money (where each unit costs a fixed price), a recursive function can determine the maximum number of units by repeatedly subtracting the unit price until the remaining money is less than the cost — just like counting backwards. This same logic applies to calculating change or dividing goods among customers at a market stall in Dar es Salaam or Arusha.
Jinsi utakavyotathminiwaTathmini ya mchakato · Tathmini ya matokeo · Tathmini ya maarifa
Tathmini ya mchakato
The student should be able to:
- Define recursivefunctions with proper base and recursive cases.
- Debug and trace recursive calls using visual tools or debugging software.
- Recognize when recursion is a suitable approach for problem-solving.
Tathmini ya matokeo
Recursive functions execute correctly and return expected results that are consistent with program specifications.
Tathmini ya maarifa
Methods used: The trainee should explain how to:
- Identify problems suitable for recursion.
- Write recursive functions with proper base cases and recursive logic.
Principles: The student should explain the principle of:
- Recursive problem-solving, including base case and recursive case design.
- Trade-offs between recursion and iteration in terms of performance and clarity.
Theories: The trainee should explain: The trainee should explain:
- How recursion simplifies solving problems with repetitive or nested substructures.
- The concept of divide-and-conquer and its implementation via recursion.
Detailed knowledge about:
- Common pitfalls in recursive programming and how to prevent them.
- Real-world applications of recursion.
Swali
What is a recursive function in programming?
Ingia ili kuwasilisha jibu lako na lihesabiwe katika umahiri wako.
Ingia ili kufanya mazoeziMwalimu
Umekwama? Niulize chochote kuhusu mada hii.
Ingia ili kumuuliza Mwalimu wa AI wa Sonza kuhusu swali hili.
Ingia ili kuulizaMajadiliano
Hakuna maswali bado