java 编写递归程序
时间: 2023-02-28 11:52:13 浏览: 87
在 Java 中,递归程序的编写需要遵循以下步骤:
1. 定义递归条件:在递归程序的开头,需要确定一个基线条件,当遇到这个条件时,递归程序将不再进行递归。
2. 定义递归步骤:在递归程序中,需要定义一个递归步骤,这一步会将原问题转化为一个规模更小的子问题。
3. 调用递归程序:在递归步骤中,需要调用递归程序本身,将规模更小的子问题交给递归程序进行处理。
示例:求 n 的阶乘
```
public static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
```
在这个示例中,递归条件为 `n == 0`,递归步骤为 `n * factorial(n - 1)`,递归调用为 `factorial(n - 1)`。
相关问题
请用JAVA编写程序实现递归算法的快速排序
好的,我可以回答这个问题。以下是使用JAVA编写递归算法的快速排序程序:
```
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
这是一个基于递归算法的快速排序程序,可以对整型数组进行排序。
java程序编写傅里叶算法
以下是Java程序编写傅里叶算法的示例代码:
```java
public class FFT {
// 计算FFT
public static Complex[] fft(Complex[] x) {
int N = x.length;
// 递归终止条件
if (N == 1) {
return new Complex[] { x[0] };
}
// 计算偶数项和奇数项
Complex[] even = new Complex[N / 2];
Complex[] odd = new Complex[N / 2];
for (int k = 0; k < N / 2; k++) {
even[k] = x[2 * k];
odd[k] = x[2 * k + 1];
}
// 递归计算偶数项和奇数项的FFT
Complex[] q = fft(even);
Complex[] r = fft(odd);
// 合并结果
Complex[] y = new Complex[N];
for (int k = 0; k < N / 2; k++) {
double kth = -2 * k * Math.PI / N;
Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
y[k] = q[k].plus(wk.times(r[k]));
y[k + N / 2] = q[k].minus(wk.times(r[k]));
}
return y;
}
// 测试
public static void main(String[] args) {
// 定义输入序列
Complex[] x = new Complex[8]; x[0] = new Complex(1, 0);
x[1] = new Complex(2, 0);
x[2] = new Complex(3, 0);
x[3] = new Complex(4, 0);
x[4] = new Complex(3, 0);
x[5] = new Complex(2, 0);
x[6] = new Complex(1, 0);
x[7] = new Complex(0, 0);
// 计算FFT
Complex[] y = fft(x);
// 输出结果
for (int i = 0; i < y.length; i++) {
System.out.println(y[i]);
}
}
}
```
该示例代码中,我们定义了一个Complex类来表示复数,并实现了复数的乘法、加法和减法运算。fft方法使用递归的方式进行快速傅里叶变换,最终返回变换后的结果。在main方法中,我们给定了一个输入序列,然后调用fft方法进行变换,并输出结果。