Как рекурсивная функция возвращает результат в Scala?

Question

В настоящее время я изучаю Scala и застрял в следующем: у меня есть этот алгоритм, который рекурсивно находит факториал числа:

 def fact(n:Int): Int=
    { 
        if(n == 1) 1
        else n * fact(n - 1) 
    } 
    println(fact(5))

Мой вопрос: почему эта строка: if(n == 1) 1 точно? Означает ли это, что функция должна возвращать единицу или n должно стать 1? Я не понимаю, как эта функция возвращает 120, что является результатом. Может ли кто-нибудь помочь мне? Я ценю любую помощь, которую вы можете оказать

Answer 1

Хм, это очень широкий вопрос.
Так как вы просите базового понимания операторов языка. Я постараюсь объяснить вам все это, но я бы порекомендовал вам пройти официальное введение в курс программирования.

В Scala все является выражением. Таким образом, сама функция является выражением, которое оценивает присвоенный блок .
. В этом случае блок является просто выражением if / else, которое принимает предикат чтобы решить, какую из двух ветвей выбрать. В этом случае n == 1 проверяет, равно ли n равному 1, если это правда, то возвращает 1, если нет, возвращает n * fact(n -1).

Таким образом, если мы выполним алгоритм самостоятельно, используя «эквациональное рассуждение» , мы сможем понять, как он работает.

fact(3) = if (3 == 1) 1 else 3 * fact(3 - 1) // replace n in the block.
fact(3) = 3 * fact(2) // reduce the if and the subtraction.
fact(3) = 3 * (if (2 == 1) 1 else 2 * fact(2 - 1)) // expand the fact definition.
fact(3) = 3 * (2 * fact(1)) // reduce the if and the subtraction.
fact(3) = 3 * (2 * (if (1 == 1) 1 else 1 * fact(1 - 1))) // expand the fact definition.
fact(3) = 3 * (2 * (1)) // reduce the if.
fact(3) = 6 // reduce the multiplications.

Answer 2

Позволяет сделать этот метод более ориентированным на c. Может быть, теперь более ясно, что есть две ветви1. Когда n равно 1 - это останавливает рекурсию. 2. В противном случае - умножьте текущее значение n на результат вызова метода факта с n - 1, который в итоге становится равным 1 и останавливает рекурсию.

def fact(n:Int): Int=
{ 
    if (n == 1) {
       (return) 1;
    }
    else {
       (return) n * fact(n - 1);
    }
}

Точка с запятой избыточна, а возврат aКлючевое слово не рекомендуется / необходимо. Вы можете прочитать об этом здесь

Так что у вас осталось:

def fact(n:Int): Int=
{ 
    if (n == 1) {
       1
    }
    else {
        n * fact(n - 1)
    }
}

Что в основном совпадает с:

def fact(n:Int): Int=
{ 
    if (n == 1) 1;
    else n * fact(n - 1)
}