재귀함수는 함수가 직접 또는 간접적으로 자기자신을 호출하는 함수.
일반적인 함수의 동작
public class RecursionSample {
public static void main(String[] args) {
sayHi();
}
public static void sayHi() {
System.out.println("hi");
}
}
재귀함수의 동작
public class RecursionSample {
public static void main(String[] args) {
sayHi();
}
public static void sayHi() {
System.out.println("hi");
sayHi();
}
}
StackOverflowError 가 발생합니다.
StackOverflowError를 막기 위해서는 재귀함수의 종료지점을 제대로 지정하고 구현해야 합니다.
*StackOverflowError?- JVM은 각 쓰레드의 각 스택에게 메모리를 할당해줍니다. 스택오버플로우 에러는 사용가능한 메모리가 더 이상 없을 때 발생합니다.
public class RecursionSample {
public static void main(String[] args) {
sayHi(5);
}
public static void sayHi(int num) {
System.out.println(num+"hi");
if(num==0) return;
sayHi(--num);
}
}
예제 1
주어지는 숫자까지의 합
public class RecursionSample {
public static void main(String[] args) {
System.out.println(sum(5)); //5+4+3+2+1 = 15
}
public static int sum(int num) {
if(num==0) return num;
return num+sum(--num);
}
}예제 2
https://leetcode.com/problems/fibonacci-number/
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
class Solution {
public int fib(int n) {
if(n<=1) return n;
else return fib(n-1)+fib(n-2);
}
}참고
https://www.youtube.com/watch?v=k-7jJP7QFEM
