2013-09-17 7 views
1

Привет, ребята, у меня есть то, что мой мозг с трудом пытается понять. Моя домашняя работа - иметь «x» кроликов. Он рекурсивно вычисляет общее количество ушей кролика. У пронумерованных кроликов нормальные два уха, у нечетных пронумерованных кроликов 3 уха, но у каждого пятого кролика 1 ухо. Мой код завершения и работа ... Вот она ...Как внедряется метод рекурсии?

import java.util.*; 

public class bunnies 
{ 
    public static int y; 

    public static void main(String[] args) 
    { 
     y = 0; 
     System.out.println(BunnyEars(3)); 
    } 

    public static int BunnyEars(int x) 
    { 
     if ((x % 5) == 0 && x != 1 && x != 0) 
      return 1 + BunnyEars(x - 1); 
     else if ((x % 2) == 0 && x != 0) 
      return 2 + BunnyEars(x - 1); 
     else if ((x % 2) != 0 && x != 0) 
      return 3 + BunnyEars(x - 1); 
     else 
      return 0; 
    } 
} 

Мой вопрос в том, как в мире делает первый ряд ушей аккумулировать ко второму ряду ушей и так далее? Я думал об именовании глобальной переменной для int y = 0; , а затем

if ((x % 5) == 0 && x != 1 && x != 0) 
    y += 1; 
else if ((x % 2) == 0 && x != 0) 
    y += 2; 
else if ((x % 2) != 0 && x != 0) 
    y += 3; 
else 
    return 0; 
return y + BunnyEars(x -1); 

Я думаю, что это имеет смысл, потому что у накапливается, но это не так. Можете ли вы, ребята, объяснить, как другой накапливается, а не y? Чин!

+0

« Именование глобальной переменной для int y = 0 ». Java не имеет глобальных переменных. Лучшая идея здесь. Рекурсивные методы * передать все, что нужно для следующего вызова * in. – hexafraction

+1

Если ваше задание специально предназначено для использования рекурсии, вам не следует использовать «глобальную» переменную. –

+0

@hexafraction Я думаю, что «глобальный» он означает переменную класса. –

ответ

4

Итак, для BunnyEars (5) давайте проследим его.

BunnyEars(5) 
1 + BunnyEars(4) 
1 + 2 + BunnyEars(3) 
1 + 2 + 3 + BunnyEars(2) 
1 + 2 + 3 + 2 + BunnyEars(1) 
1 + 2 + 3 + 2 + 3 + BunnyEars(0) 
1 + 2 + 3 + 2 + 3 + 0 

Обратите внимание, что никакое добавление фактически не происходит до последнего вызова BunnyEars. Каждый раз, когда он пытается добавить результат рекурсивного вызова, он должен ждать возврата, который затем вызовет новый и т. Д. Затем он работает обратно, возвращаясь ко всем методам, добавляя результат по пути, прежде чем, наконец, вернет результат для вызывающего абонента.

+0

И отвечает ли это на вопрос полностью? – hexafraction

+1

@hexafraction, видя, как это выполняется, является лучшим способом продемонстрировать рекурсию. Вы можете увидеть скопление здесь. – Cruncher

+1

@hexafraction ответ, который получил upvote, был таким же, как мой, за исключением того, что они вставили его метод. – Cruncher

1

Попробуйте разбить его в случайном порядке.

Скажем, у вас нет зайчиков

BunnyEars(0) вернется 0, потому что он не идет ни в одну из других случаев.

Скажем, у вас есть один кролик

BunnyEars(1) вернется 3 + BunnyEars(0), который мы уже знаем, является 0. Поэтому он будет оцениваться до 3 + 0, который равен 3.

Скажем, у вас есть два зайчики

BunnyEars(2) вернется 2 + BunnyEars(1), который мы уже знаем, является 3. Поэтому он будет оцениваться до 2 + 3, который равен 5.

Продолжите с этим шаблоном, и он должен проиллюстрировать, как рекурсивно пройти эту логику.

7

Вот ваш метод:

public static int BunnyEars(int x) 
{ 
    if ((x % 5) == 0 && x != 1 && x != 0) 
     return 1 + BunnyEars(x - 1); 
    else if ((x % 2) == 0 && x != 0) 
     return 2 + BunnyEars(x - 1); 
    else if ((x % 2) != 0 && x != 0 
      ) 
     return 3 + BunnyEars(x - 1); 
    else 
     return 0; 
} 

Вот гипотетический пример вызова:

BunnyEars(7) 

Это становится

return 3 + BunnyEars(6) 

Который становится

return 3 + 2 + BunnyEars(5) 
return 3 + 2 + 1 + BunnyEars(4) 
return 3 + 2 + 1 + 2 + BunnyEars(3) 
return 3 + 2 + 1 + 2 + 3 + BunnyEars(2) 
return 3 + 2 + 1 + 2 + 3 + 2 + 3 + BunnyEars(0) 
return 3 + 2 + 1 + 2 + 3 + 2 + 3 + 0 
return 16 

Предложенное улучшение кода: Добавить статью в сторожевую к началу:

if (x == 0) return 0; 

После этого вы можете удалить все && x != 0 с в if отчетности. Это очень сильно очистит код.

У вас также есть много посторонних скобок - (x % 2) == 0 - это то же самое, что и x % 2 == 0.

Улучшен код:

public static int BunnyEars(int x) 
{ 
    if (x < 0) throw new IllegalArgumentException("Bunnies cannot be negative"); // handle bad input 
    if (x == 0) return 0; 
    if (x % 5 == 0) // no need for `&& x != 1` because 1 % 5 isn't 0 anyway 
     return 1 + BunnyEars(x - 1); 
    else if (x % 2 == 0) 
     return 2 + BunnyEars(x - 1); 
    else if (x % 2 != 0) 
     return 3 + BunnyEars(x - 1); 
} 
+0

Это действительно одна из тех вещей, после того как он прочитал ее 5 раз, это будет иметь смысл. – Cruncher

+0

Итак, когда мы добираемся до последней части «return 0;» он не вернется 0 он вернет 16 + 0? – Isaac

+0

@DavidCamacho Ну, он возвращает '0' ** до последней итерации, которая называлась **, поэтому' 0' суммируется с общим значением. 'return 3 + 2 + 1 + 2 + 3 + 2 + 3 + BunnyEars (0)' становится 'return 3 + 2 + 1 + 2 + 3 + 2 + 3 + 0'. – Doorknob

1

Я дам другому, проще, рекурсивный пример. Скажем, мы хотим, чтобы сумма всех целых чисел до п:

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

Давайте назовем эту функцию для п равно 0. Конечно, проверка прошла успешно, и мы получаем 0 в качестве возвращаемого значения.

Назовем эту функцию для n равным 1. Проверка завершается с ошибкой, поэтому мы возвращаем 1 плюс результат sumUpTo(0). Мы уже знаем, что этот результат равен 0, поэтому конечный результат равен 1. Можно сказать, что результат 1 + sumUpTo(1 - 1) = 1 + sumUpTo(0) = 1 + 0 = 1.

Для 2 мы получаем звонок: 2 + sumUpTo(2 - 1) = 2 + sumUpTo(1) = ... = 3. И так далее. Накопление, которое вы хотели, сделано на лету.

5

Я думал, называя глобальную переменную для int y = 0, а затем

Нет, глобальная переменная не должна использоваться там (хотя наличие локальной переменной может дать вам немного больше ясности):

if (x == 0) return 0; // Zero bunnies --> zero ears 
int y = 0; // Variable y represents the number of ears that bunny number x has 
if ((x % 5) == 0 && x != 1 && x != 0) 
    y = 1; 
else if ((x % 2) == 0 && x != 0) 
    y = 2; 
else if ((x % 2) != 0 && x != 0) 
    y = 3; 
return y + BunnyEars(x -1); 

Уловка этой (и любой другой) рекурсивной функции понимает, что существует более одного x. Так как функция вызывает себя с другим аргументом, поэтому каждый вызов имеет свой собственный x.

Вот как последовательность вызовов и возвратов выглядит:

BunnyEars(x==6) 
    Compute y for x==6 // That's 2 
    Call BunnyEars(x==5) 
     Compute y for x==5 // That's 1 
     Call BunnyEars(x==4) 
      Compute y for x==4 // That's 2 
      Call BunnyEars(x==3) 
       Compute y for x==3 // That's 3 
       Call BunnyEars(x==2) 
        Compute y for x==2 // That's 2 
        Call BunnyEars(x==1) 
         Compute y for x==1 
         Call BunnyEars(x==0) 
         return 0 // Zero bunnies --> zero ears 
        return 2+0 --> 2 
       return 3+2 --> 5 
      return 2+5 --> 7 
     return 1+7 --> 8 
    return 2+8 --> 10 

После того, как вы видите, что более чем один вызов BunnyEars активен в то же время, это должно начать, чтобы понять: цепочка вызовов продолжается, не возвращаясь до тех пор, пока он не достигнет x==0 «Без зайчика - никаких ушей!", в этот момент цепочка начинает разворачиваться, добавляя правильное количество ушей к возвращаемому значению предыдущего вызова.

Смежные вопросы