CPT 102_Java

CPT 102

1. Recursive functions 【递归函数】

A recursive function is a function that calls itself directly or indirectly
Related to recursive problem solving: binary tree traversal (divide & conquer)
The function knows how to solve a base case (stopping rule)
A recursion step is needed to divide the problem into sub-problems (key step)
Need to check for termination

2. Factorial function 【阶乘函数】

2.1. Design 2.1.1. Base Case

Number = 0 || Number = 1
Result = 1

2.1.2. Recursive step

Number > 1
Result = Number x (Number - 1)!

2.2. Java Code 2.2.1.Java Code

import java.util.Scanner;

public class Factorial {
    public static void main(String[] args) {
        Scanner kb =new Scanner(System.in);
        System.out.println("Enter the number");
        int input = kb.nextInt();
        System.out.println("Result"+factorial(input));
    }

    public static int factorial(int input){
        //input
        if (input<0){
            return -1;
        }
        else if (input==0 ||input ==1){
            return 1;
        }else {
            return input*factorial(input-1);
        }
    }
}

3. Fibonacci function 【斐波那契数组】

3.1. Design 3.1.1. Base Case

fibonacci(0) = 0
fibonacci(1) = 1

3.1.2. Recursive step

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

3.1.3. How does it works?

3.2. Java Code 3.2.1.Java Code

import java.util.Scanner;

public class Fibonacci {
    public static void main(String[] args) {
        Scanner kb =new Scanner(System.in);
        System.out.println("Enter the number");
        int input = kb.nextInt();
        System.out.println("Result: "+fibonacci(input));
    }

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

4. Recursion vs iteration

4.1. Recursion vs iteration 4.1.1. Use

Iteration uses an iterative structure, while for
Recursion uses a selection structure & function calls

4.1.2. Termination test

Iteration ends when the continuation condition fails
Recursion ends when a base case recognized

4.1.3. Features

Iteration
- Efficient but not easy to design
Recursion
- Slow (cost memory & processor power) but elegant

4.1.4. Info

Every recursive function can be rewritten as an iterative function

5. Q & A

What is the key step in designing a recursive function?
- A recursion step is needed to divide the problem into sub-problems
Every recursive function can be rewritten as an iterative function. (T or F)
- T

CPT 102

Java相关栏目本月热门文章