Рекурсія

Рекурсією називається метод (функція), яка всередені свого тіла визиває сама себе.
взято із сайту http://kostin.ws/java/java-static-methods.html

Разглянемо приклад — обчислення факторіалу. Для того щоб обчислити n!, достатньо знати  (n-1)! та помножити на n.

import java.util.*;
public class dodatvid {
   
    static int fact (int n) {
          if (n==1) {
            return 1;
          } else if (n==2) {
            return 2;
          } else {
            return fact(n-1) * n;
          }
        }
    public static void main(String[] args) {        int f=5;
        System.out.println(f+"!="+fact(f));

    }
}


Розглянемо приклад, який обчислюэ через рекурсыю n-те число Фібоначчі.
Нагадаємо, як виглядають перші елементи цього ряду: 1 1 2 3 5 8 13 …

import java.util.*;
public class dodatvid {
   
    static int fib (int n) {
          if (n==1 || n == 2) {
            return 1;
          }
          return fib (n-2) + fib (n-1);
        }
    
    public static void main(String[] args) {
        int f=20;
        System.out.println(f+"-те число Фібоначі = "+fib(f));
     }
}

Зверніть увагу, що в цьому методі другий return не поміщений у блок else для першого умовного оператора. Це допустимо, адже якщо виконається умова і спрацює перший return, то станеться вихід з методу, до другого return виконання програми дійде тільки у разі невиконання умови.

Рекурсивні обчислення часто призводять до необхідності повторювати одні і ті ж дії, що істотно уповільнює роботу програми.

Намалювати
-
--
---
----
-----
n- разів використовуючи процедуру.

import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] argv) throws IOException{
new Main().run();
}

void F(int n, int k)
{
    if (n>0){
    for (int i=1;i<=k;i++) pw.print('-');
    pw.println();
    F(n-1, k+1);
    }
 }

PrintWriter pw;
Scanner sc;
public void run() throws IOException{
sc = new Scanner(new File("input.txt"));

pw = new PrintWriter(new File("output.txt"));
pw = new PrintWriter(System.out);
int n=14; // або     n=sc.nextInt();
F(n,1); // n- кількість ланок, 1 - довжина ланки

pw.close();
}
}


Вивести всі n-значні числа

import java.util.*;
import java.io.*;
public class Main{

public static void main(String[] argv) throws IOException{
new Main().run();
}
///////////////////////////////////////////
void f(int m, String s){
    if (m>0)
    for (int i=0;i<=9;i++){
        f(m-1,s+i);
        }
    else if (s.charAt(0)!='0')pw.println(s);
}
////////////////////////////////////////////
PrintWriter pw;
Scanner sc;
public void run() throws IOException{
sc = new Scanner(new File("input.txt"));
pw = new PrintWriter(new File("output.txt"));
int n=sc.nextInt();
f(n,"");
pw.println();
pw.close();
}
}

Завдання

1. З'ясуйте експериментальному шляхом, починаючи з якого елементу послідовності Фібоначчі, обчислення з використанням рекурсії стає неприйнятним(займає більше хвилини за часом).
2. Створіть гібридний метод, для невеликих n що обчислює n- ое число Фібоначчі за допомогою рекурсії, а для значень, що перевищують з'ясоване вами в попередньому завданні порогове n, що обчислює n- ое число Фібоначчі за допомогою ітераційного алгоритму(циклу, у рамках якого зберігатимуться значення двох попередніх елементів послідовності).