Recursion

Recursion in programming is a technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. It is particularly useful for solving problems that can be divided into smaller instances of the same problem, such as tree traversal, sorting algorithms like quicksort, or calculating factorials. Recursion provides an elegant and concise solution to complex problems, often leading to cleaner and more understandable code. However, excessive recursion can lead to stack overflow errors, so it's important to ensure proper termination conditions and optimize recursive algorithms when necessary.

Select Languages

Examples

C

#include <stdio.h>

int getSum( int arr[], int index ) {
  if (index < 0) {
    return 0;
  }
  return arr[index] + getSum(arr, index-1);
}

int testArr[] = {1, 2, 4, 5};
int sum = getSum(testArr, 3);
printf("%d", sum);

C#

using System.Collections.Generic;

int getSum(List<int> arr) {

  if (arr.Count == 0) return 0;
  int firstVal = arr[0];
  arr.RemoveAt(0);
  Console.WriteLine(firstVal +"\n");
  
  return firstVal + getSum(arr);
}

List<int> testArr = new List<int>();
testArr.Add(1);
testArr.Add(2);
testArr.Add(4);
testArr.Add(5);

int sum = getSum(testArr);
Console.WriteLine(sum);

C++

#include <iostream>
#include <queue>
using namespace std;

int getSum (queue<int> arr) {
  if (arr.size() == 0) {
    return 0;
  }
  int firstVal = arr.front();
  arr.pop();
  return firstVal + getSum(arr);
}

queue<int> testArr;
testArr.push(1);
testArr.push(2);
testArr.push(3);
testArr.push(5);

int sum = getSum(testArr);
cout << sum << endl;

Go

import "fmt"

func getSum (arr []int) int {
   if (len(arr) == 0) {
     return 0
   }
   firstVal := arr[0]

   // slice first element
   arr = arr[1:]
   fmt.Println(firstVal)
   fmt.Println(arr)
   return firstVal + getSum(arr)
}

testArr := []int{1, 2, 4, 5}
sum := getSum(testArr);
fmt.Println(sum)

Java

import java.util.ArrayList;

public static int getSum(ArrayList<Integer> arr) {

  if (arr.size() == 0) return 0;
  int firstVal = arr.get(0);
  arr.remove(0);
  System.out.println(firstVal );
  
  return firstVal + getSum(arr);
}

ArrayList<Integer> testArr = new ArrayList<>();
testArr.add(1);
testArr.add(2);
testArr.add(4);
testArr.add(5);

int sum = getSum(testArr);
System.out.println(sum );

JavaScript

function getSum (arr) {
   if (arr.length === 0) return 0;
   const firstVal = arr.shift();
   console.log(firstVal);
   return firstVal + getSum(arr);
}

const testArr = [1, 2, 4, 5]
const sum = getSum(testArr);
console.log(sum);

Kotlin

fun getSum(arr:MutableList<Int>):Int {
  if(arr.count() == 0) return 0;
  var firstVal = arr[0];
  arr.removeAt(0);
  
  return firstVal + getSum(arr);
}

var testArr =
  mutableListOf<Int>(1, 2, 4, 5);
  
val sum = getSum(testArr);
println(sum);

MatLab

function result = getSum(arr)
  if 1:length(arr) == 1;
    result = arr(1)
  else
    val = arr(1);
    arr(1)=[];
    secVal = getSum(arr)
    result = val + secVal;
  end
end

testArr = [1, 2, 4, 5];
result = getSum(testArr);

disp(result);

PHP

function getSum($arr) {
  if (sizeof($arr) == 0) return 0;
  $val = $arr[0];
  array_shift($arr);
  return $val + getSum($arr);
}

$testArr = array(1, 2, 4, 5);
$sum = getSum($testArr);
echo $sum;

Python

def getSum(arr):
  if len(arr) == 0:
    return 0
  firstVal = arr[0]
  arr.pop(0)
  return firstVal + getSum(arr)

testArr = [1, 2, 4, 5]
sum = getSum(testArr)
print(sum)

R

getSum <- function(arr) {
  if (length(arr) == 1) {
    return (arr[1])
  } else {
    val <- as.numeric(arr[1])
    arr <- arr[-1]
    secondVal <- getSum(arr)
    return(val + as.numeric(secondVal))   
  }
}

testArr <- list(1, 2, 4, 5)
sum <- getSum(testArr)
print(sum)

Ruby

def getSum(arr)
  return 0 if arr.empty?
  
  firstVal = arr[0];
  arr.shift();
  return firstVal + getSum(arr);
end

testArr = Array[1, 2, 4, 5]
sum = getSum(testArr)
puts sum

Rust

use std::collections::VecDeque;

fn getSum(arr:VecDeque<usize>) -> usize {
  // needs to become mutable
  let mut copy = arr;

  if copy.len() == 0 {
  return 0;
  }

  let val = copy[0];
  copy.remove(0);
  return val + getSum(copy);
}

let mut testArr = VecDeque::new();

testArr.push_back(1);
testArr.push_back(2);
testArr.push_back(4);
testArr.push_back(5);

let sum = getSum(testArr);
println!("{}", sum);

Scala

import scala.collection.mutable.Queue;

def getSum(arr: Queue[Int]): Int = {
  if (arr.length == 0) return 0;
  var curVal = arr.front;
  arr.dequeue();
  return curVal + getSum(arr);
}

var testArr = Queue(1, 2, 4, 5);
var sum = getSum(testArr);
println(sum);

Swift

func getSum(arr: Array<Int>) -> Int {
  var copy = arr;
  if copy.count == 0 {
      return 0;
  }
  
  let val = copy[0];
  copy.removeFirst();
  return val + getSum(arr:copy);
}

var testArr = [1, 2, 4, 5];
var sum = getSum(arr: testArr);
print(sum)

TypeScript

function getSum (arr:number[]):number {
   if (arr.length === 0) return 0;
   const firstVal = arr.shift();
   console.log(firstVal);
   return firstVal + getSum(arr);
}

const testArr:number[] = [1, 2, 4, 5]
const sum = getSum(testArr);
console.log(sum);

Copyright 2025. All Rights Reserved. IronCodeMan.