Recursion

Numerical / Logical


20852
Write a method called fact that recursively calculates the factorial value of its single int parameter. The value returned by fact is a long ..



public long fact(int n) {
if (n <= 1) {
return 1;
} else {
return (fact(n-1) * (long) n);
}
}


20854
The sum of the numbers from 1 to n can be defined recursively as follows:
The sum from 1 to 1 is 1.
The sum from 1 to n is n more than the sum from 1 to n-1. Write a int -method named sum that accepts an int parameter, n, and recursively calculates and returns the sum of the numbers from 1 to n. .


public int sum(int n) {
if (n == 1) {
return 1;
} else {
return (sum(n-1) + n);
}
}


21210
Consider a simple form of integer division: m / k where we are guaranteed that m>=0 and k>0. This can be computed as follows
The quotient is 0 when k is greater than m.
Otherwise, the quotient is one more than (m-k)/k Write ab int -method named quotient that accepts two int parameter, m and k, and recursively calculates and returns the integer quotient of m/k. You can count on m>=0 and k>0. Do not use a division operator here! .


int quotient(int m, int k) {

if(k==1)
return m;
if(k>m)
return 0;
return quotient(m-k, k) +1;
}


20855
Given non-negative integers x and n, x taken to the nth power can be defined as:
x to the 0th power is 1
x to the nth power can be obtained by multiplying x to the n-1'th power with x Write a long -valued method named power that accepts an two int parameters x and n (in that order) and recursively calculates and returns the value of x taken to the n'th power.

int power(int x,int n)
{
if(n==1)
return x;
if(n==0)
return 1;

return power(x, n-1) * x;
}


20853
Two non-negative integers x and y are equal if either:
Both are 0, or
x-1 and y-1 are equal Write a boolean -method named equals that recursively determines whether its two int parameters are equal and returns true if they are and false otherwise.

boolean equals (int x, int y)
{
if( (x<0) || (y<0) ) return false;
if( (x==0) && (y==0) ) return true;
return equals(x-1, y-1);
}

21231
The nth harmonic number is defined non-recursively as: 1 +1/2 + 1/3 + 1/4 + ... + 1/n. Come up with a recursive definition and use it to guide you to write a method definition for a double -valued method named harmonic that accepts an int parameters n and recursively calculates and returns the nth harmonic number.


double harmonic(int N)
{
if (N == 0) {
return 0.0;
} else {
return (1.0/N + harmonic(N-1));
}
}

The Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13, 21, has as its first 2 values, 0 and 1; each successive value if then calculated as the sum of the previous two values.
The first element in the series is the 0'th element, thus the value 8 is element 6 of the series.
The n'th element of the series, written as fib(n), is thus defined as:
n if n = 0 or n = 1
fib(n-1) + fib(n-2) Write the int-valued method fib, that takes a single int parameter (say n), and recursively

public static int fib(int n)
{
if(n==0)
return 0;
else if(n<=2)
return 1;
return fib(n-1)+fib(n-2);
}


The "odd/even factorial" of a positive integer n is represented as n  and is defined non-recursively as: (n)(n-2)(n-4)...(4)(2) if n is even and is (n)(n-2)(n-4)...(5)(3) (1) if n is odd. For example 7  equals 7*5*3*1 or 105 and 6  equals 6*4*2 or 48. Come up with a recursive definition for n  and use it to guide you to write a method definition for a method called oddevenfact that recursively calculates the odd/even factorial value of its single int parameter. The value returned by oddevenfact is a long ..




long oddevenfact(int x)
{
if (x>2)
return(oddevenfact(x-2) * (long) x);
else
return((long) x);
}