Recursion is a technique where a function calls itself to solve a problem by breaking it down into smaller sub-problems.
Base Condition
Every function call in recursion is stored in the call stack. If the recursion is too deep or has no base condition, the call stack keeps growing until memory is exhausted, causing a stack overflow error.
A base condition is essential in recursion. It stops the recursion when a certain condition is met. Without it, recursion goes infinite and causes a stack overflow.
if (num === 0) return;Approach
Problem: Print numbers from n to 1 using recursion.
- Print the number.
- Recurse with
num - 1. - Stop when
num === 0.
Time & Space Complexity
- Time Complexity: O(n) – one function call per number from n to 1.
- Space Complexity: O(n) – due to recursive call stack frames.
function printDescending(num) {
if (num === 0) return;
console.log(num);
printDescending(num - 1);
}
printDescending(5);
#include <stdio.h>
void printDescending(int num) {
if (num == 0) return;
printf("%d\n", num);
printDescending(num - 1);
}
int main() {
printDescending(5);
return 0;
}
#include <iostream>
using namespace std;
void printDescending(int num) {
if (num == 0) return;
cout << num << endl;
printDescending(num - 1);
}
int main() {
printDescending(5);
return 0;
}
public class Main {
static void printDescending(int num) {
if (num == 0) return;
System.out.println(num);
printDescending(num - 1);
}
public static void main(String[] args) {
printDescending(5);
}
}
def print_descending(num):
if num == 0:
return
print(num)
print_descending(num - 1)
print_descending(5)
using System;
class Program {
static void PrintDescending(int num) {
if (num == 0) return;
Console.WriteLine(num);
PrintDescending(num - 1);
}
static void Main() {
PrintDescending(5);
}
}
