Module $2$: Lab $3-$ Review Linear Recursion

Linear Recursion

This lab is made to help you review$/$learn basic recursion. The next lab will get a little trickier as you move from linear to branching

recursion.

What is recursion?

Linear recursion is when a function calls itself without branching out into multiple function calls. A good example of this would be a

factorial function, $f(n)=n!$

Why is factorial linear in a recursive sense? Lets take $f(5),$ for example. To compute this we need to do: $1*2*3*4*5=120$

In other words we are doing $f(4)*5$ or $f(3)*4*5$ and so on until we get to $f(0),$ which is considered to be the base case.

This function will only have one recursive call to itself, meaning if you draw out the stack trace each call will point to another in a linear

fashion.

This displays two important definitions: the recursive call and the base case.

A recursive call is when a function in code calls itself, and the base case is a condition in which causes the function to eventually

terminate. Without a base case, a recursive function will go indefinitely until you get what is called a stack overflow $($too many recursive

calls for the stack to handle$).$ Java will throw a runtime error if you create a recursive function which overflows.

Lab Assignment

The best way to get an idea of how recursion works is to practice. In the code given to you, complete the unfinished methods and run them

with the given test cases.

The following $.$java files are included in this lab:

L$3$

LinearRecursion.java

The Factorial Method

The first method we are going to modify is the Factorial Method.

TO DO:

Write this method so that it returns the factorial for any input integer $n.n!$ is $n**(n-1)**(n-2)**dots*1.$

The Summation Method

The next method we are going to modify is the Summation Method. This method is similar to factorial but instead of multiplying each

element you will add them together.The Summation Method

The next method we are going to modify is the Summation Method. This method is similar to factorial but instead of multiplying each

element you will add them together.

TO DO:

Write this method so that when you input an integer $n$ the method will return $n+(n-1)+(n-2)+$dots$+1.$

The Harmonic Summation Method

The Harmonic Summation will return the sum of the harmonic series.

TO DO:

Set up this method so that when you input an integer $n$ the method will return the sum of $1+\frac{1}{2}+\frac{1}{3}+$dots$+\frac{1}{n-1}+\frac{1}{n}.$

The Geometric Summation Method

The Geometric Summation will return the sum of the geometric series.

TO DO:

Set up this method so that when you input an integer $n$ the method will return the sum of the sum $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+$dots$+$

$1/$Math$.$pow $(2,n),$

To understand how these methods are exhibiting linear recursion, draw out the stack trace for a reasonable $n$ value like $4.$ Here's an

example of this for factorial for $n=5$ :If you've implemented everything correctly your output should look like this: