Basic Recursion Programs

1.Sum of Digits

 Example:

123 → 1 + 2 + 3 = 6
--> add all digits of a number

Formula
sum(n) = (n % 10) + sum(n / 10)

java

public class Main {
    static int sumDigits(int n) {
        if (n == 0) return 0;
        return (n % 10) + sumDigits(n / 10);
    }

    public static void main(String[] args) {
        System.out.println(sumDigits(123));
    }
}

python

def sum_digits(n):
    if n == 0:
        return 0
    return (n % 10) + sum_digits(n // 10)

print(sum_digits(123))

javascript

 function sumDigits(n) {
  if (n === 0) return 0;
  return (n % 10) + sumDigits(Math.floor(n / 10));
}

console.log(sumDigits(123));

output

2.Count Digits in a Number

 Example:
       12345 → 5 digits
     --> find how many digits are in a number

Formula
count(n) = 1 + count(n / 10)

Java

public class Main {
    static int countDigits(int n) {
        if (n == 0) return 0;
        return 1 + countDigits(n / 10);
    }

    public static void main(String[] args) {
        System.out.println(countDigits(12345));
    }
}

python

def count_digits(n):
    if n == 0:
        return 0
    return 1 + count_digits(n // 10)

print(count_digits(12345))

javascript

function countDigits(n) {
  if (n === 0) return 0;
  return 1 + countDigits(Math.floor(n / 10));
}

console.log(countDigits(12345));

output

3. Power of a Number (x^n)
Formula:
xⁿ = x × xⁿ⁻¹
the function calls itself with smaller values.

   Example:

       2⁴ = 2 × 2 × 2 × 2 = 16
       3³ = 3 × 3 × 3 = 27

java

public class Main {
    static int power(int x, int n) {
        if (n == 0) return 1;
        return x * power(x, n - 1);
    }

    public static void main(String[] args) {
        System.out.println(power(2, 4));
    }
}

python

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)

print(power(2, 4))

javascript

function power(x, n) {
  if (n === 0) return 1;
  return x * power(x, n - 1);
}

console.log(power(2, 4));

output

4. Reverse a String
This program reverses a string by breaking it into smaller parts and solving step by step.
--> Take the first character
--> Recursively reverse the remaining string
--> Add the first character at the end

How it works

 reverse("hello")
= reverse("ello") + 'h'
= reverse("llo") + 'e' + 'h'
= reverse("lo") + 'l' + 'e' + 'h'
= reverse("o") + 'l' + 'l' + 'e' + 'h'
= reverse("") + 'o' + 'l' + 'l' + 'e' + 'h'
= "" + "olleh"

java

 public class Main {
    static String reverse(String str) {
        if (str.isEmpty()) return str;
        return reverse(str.substring(1)) + str.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(reverse("hello"));
    }
}

python

 def reverse(s):
    if s == "":
        return ""
    return reverse(s[1:]) + s[0]

print(reverse("hello"))

javascript

function reverse(str) {
  if (str === "") return "";
  return reverse(str.slice(1)) + str[0];
}

console.log(reverse("hello"));

output