[Java] Java371 Lecture 5

Methods and Recursion

info

This document is a class note about Java Programming taughted by Mr.Lu.

Methods

• Methods are used to define reusable codes, so that it could organize and simplify your programs.
• Every parameter should be declared with one specific type.
• Every method needs one return type even if it has no return!

Example: max

public static int max(int num1, int num2) {
    int result;

    if (num1 > num2)
        result = num1;
    else
        result = num2;
    return result;
}

// invoke
int z = max(10, 20); // z equals to 20

// alternative
public static int max(int num1, int num2) {
    return num1 > num2 ? num1 : num2;
}

About the return Statement

• The return statement terminates the method.
• A caller invokes one method, called the callee.
• The caller and the callee should follow the method header, like a contract.
• The caller provides the callee with adequate inputs and receives one return value from the callee (or none if the return type is void).

Method invocation

• The JVM pushes a frame into the call stack, which stores the arguments and other necessary information for each method invocation.
• Once the method reaches any return statement (or the bottom of the method), the frame will be nullified and the JVM returns to where the caller jumps from.
• It also implies that the memory space occupied by the frame will be recycled for next method invocation.

Variable Scope

• A variable scope is the region where one variable is visible.
• A variable has one of the following three scopes: class level, (method) local lvel, and loop level.
• As a local variable, any changes made inside the method does not affect the original value.
• Note that one local variable can have its name identical to the one of class level.
• This is called the shadow effect because we favor the local one.

Example

public class ScopeDemo {

    public static int x = 10; // Class level; global variable.

    public static void main(String[] args) {

        System.out.println(x); // Output 10.
        int x = 100; // Method level, aka local variable.
        x++;
        System.out.println(x); // Output 101.
        addOne();
        System.out.println(x); // Output ? I guess 11.

    }

    public static void addOne() {

        x = x + 1;
        System.out.println(x); // Output 11.

    }
}

Recursion

Recursion is a process of defining something in terms of itself.

• A method that calls itself in some way is recursive.
• Recursion is an alternative form of repetition without any loop.

Example: Factorial

info

Write a program to determine n! by recursion.

public static int factorial (int n) {

    if (n < 2)
        return 1; // base case
    else
        return n * factorial(n - 1); // recurrence relation
}

• Remember to set a base case in recursion.
• What is the time complexity?

Comparison

int s = 1;
for (int i = n; i > 1; i--) {
    s *= i;
}

• Both run in O(n) time.
• One intriguing question is , Can we always turn a recursive method into a loop version of that?
  • Affirmative.

Remarks

• Recursion bears substantial overhead.
• So the recursive algorithm may execute a bit more slowly than the iterative equivalent.
• Moreover, a deep recursion depletes the call stack, which is limited, and causes the error StackOverflowError.

Exercise: Summation

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

Exercise: Greatest Common Divisor (GCD)

info

Let a and b be two positive integers. Calculate GCD(a, b) by recursion.

• We implement the Euclidean algorithm for GCD.
• For example,

public static int gcd_by_recursion(int a, int b) {

    int r = a % b;
    if (r == 0)
        return b;
    return gcd_by_recursion(b, r);

}

Exercise: Fibonacci Sequence

info

Let n be a nonnegative integer. Calculate the n-th Fibonacci number.

public static int fib(int n) {

    if (n < 2) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }

}

public static double fib2 (int n) {

    if (n < 2) return n;

    int x = 0, y = 1;
    for (int i = 2, i <= n; i++) {
        int z = x + y;
        x = y;
        y = z;
    }
    return y; // Why not z ?

}

• The algorithm runs is O(n) time!
• Could you find the O(n)-time recursive one?
• Check out leetcode

Conclusion

• Methods are control abstarctions while data structures are data abstractions.
• We can treat the notion of objects as a way to combine data and control abstractions.
• For example, try to enumerate the data with its associated controls in your cellphone.
  • Data: phone book, photo album, music library, clips, etc.
  • Controls? The buttons you can press in those apps.
• Then let's start the object-oriented programming (OOP) paradigm in the next chapter.