How Recursion Works with Examples

Using a Loops

We could simply right this function like:

public static int summationThroughLoops(int k){
        int sum = 0;
        for(int i = 0; i < k; i++){
            sum += (i + 1);
        }
        return sum;
    }

This function will take k (the max iteration) and will iterate through as a summation.

So if k is 5, the function will do 1 + 2 + 3 + 4 + 5 = 15

Using Recursion

Now lets solve the exact same problem with Recursion:

  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }

In this function, instead of a loop, the function calls itself while k declines in that call. the intial call to the function will return k + sum(k – 1). In order for this function to actually return, it will need to run the call sum(k – 1). So what happens next?

Say k = 5 again. so the initial call would:

return 5 + sum(5 – 1)

it calls itself and sum(5 – 1) returns 4 + sum(4 – 1)

sum(4 – 1) returns 3 + sum(3 – 1)

sum(3 – 1) returns 2 + sum(2 – 1)

sum(2 – 1) returns 1 + sum(1 – 1)

sum(1 – 1) returns 0

If you then return all the way back:

sum(1 – 1) returns 0

sum(2 – 1) returns 1 + 0 = 1

sum(3 – 1) returns 2 + 1 = 3

sum(4 – 1) returns 3 + 3 = 6

sum(5 – 1) returns 4 + 6 = 10

sum(5) returns 5 + 10 = 15

Leave a Reply