RECURSION TASKS:

Please create the package recursion.

Please complete 5 tasks. You should use the recursive methods in each task. In Task1 and task 5, you can use for loop only in the main to print first k numbers (see Example 1).

Task 1. Fibonacci.java

Have a Java application with recursion that asks the user for integer number k and then generates and shows on in a row k first Fibonacci numbers.

0 1 1 2 3 5 8 13 21 34 ...

tn=tn-1+tn-2 if n<=0 -> tn=0 if n=1 -> tn=1

Task 2. Euclid.java

Euclid's Algorithm helps to find the greatest common divisor (gcd) of a pair of natural numbers (the same as the greatest common factor GCF).Find gcd (m,n)

1. If m=n then gcd(m,n) = m
2. If m>n, then gcd(m,n) = gcd(n,m-n)
3. If m

Have a java application with recursion that asks the user to enter 2 integer numbers, and then calculates and shows the greatest common divisor of these numbers.

Task 3. SumOfDigits.java

Have a recursive function that returns the sum of the digits of an integern. (Please use the following statement to ignore the sign of the number n on the beginning of the recursive method. n = Math.abs(n); )

Ex: number 5467 Sum=22

Task 4. Sequence.java

Have a recursion formula for the following sequence: 2 5 14 41 122

Have a program that asks the user for the number K and then shows first K terms of this sequence on a screen. Use recursion.

Task 5. ReversePrint.java

Have a recursive function (use no while loops or for loops) that prints all the elements of an array of integers, with one space between elements, in reverse order. The parameters to the function should be int []a, and int size.

Recursion Tasks

Another way of thinking and programming repetitions without common loop structures.

Recursion Animation: https://www.youtube.com/watch?v=Px8dgjKeh5I

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science. Most computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proventhat these recursive-only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like "while" and "for".

Example1:

1 4 13 40 121

Find the pattern formula for t_n

t_n= 3*t_n-1+1, if n> 1, and let define t_n = 1, if n=1, 0 or any other cases.

Have the method that calculates and returns t_n without loops . In the main you can use a loop to output the first k numbers in the sequence. (Printing inside a recursion method we will learn later)

import java.util.Scanner;

public class Example1 {

public static void main(String[] args){

Scanner input = new Scanner (System.in);

System.out.println("how many numbers in the sequence? ");

int k = input.nextInt();

for (int i = 1;i<=k;i++){

System.out.print(Sequence(i) + " ");

}

}

public static int Sequence(int n){

if(n>1)

return 3*Sequence(n-1)+1;//recursive part

else return 1;// terminating condition

}

}

Recursion Defined:

A method which calls itself.

The Terminating Condition or Base Case:To avoid an infinite loop: the recursion call must be conditionally executed, which means itMUST include a check for the terminating condition.

Templates of Recursion:

Three Characteristics of Recursion:

• Calls itself recursively
• Has some terminating condition
• Moves "closer" to the terminating condition.

Every recursive algorithm has 2 parts:

One part is calledthe Terminating Condition or Base Case:To avoid an infinite loop: the recursion call must be conditionally executed, which means itMUST include a check for terminating condition.

It should prevent the recursive algorithm from infinite recursion (going over and over again). Programmer needs to be sure that the solution finally will reach the base case.

Another part is called the Recursive Step. In this part the algorithm simplifies the problem and calls itself to solve the simpler problem.

Example 2:

Calculate the factorial(n)

Base Case: if (n is 0 or 1) return 1

Recursive Step: else return n* factorial(n-1)

Tracing the algorithm for n=3:

3*factorial(2)

3*2*factorial(1)

3*2*1

3*2

6

public int factorial(int n){

if(n>1){ return n*factorial(n-1);}

else return 1;

}

Please watch the following

https://www.youtube.com/watch?v=B0NtAFf4bvU

Example 3:Have a recursive function(no loops while, for or do while allowed) that calculates sum of first n integer numbers.

1+2+ +(n-1) +n sum(n)=sum(n-1)+n

public int sum(int n){

If(n>0) return sum(n-1)+n;

else return 0;}