Как эффективно визуализировать рекурсивную функцию?

В настоящее время я участвую в рекурсии обучения в классе программирования. Я заметил, как трудно для моих учеников понять концепцию рекурсии. Есть ли хороший способ визуализировать, что делает функция для педагогических целей?Как эффективно визуализировать рекурсивную функцию?

В качестве примера здесь является функция R для получения n-й число Фибоначчи:

fib_r <- function(n) { 
    if(n <= 2) return(1) 
    fib_r(n-1) + fib_r(n-2) 
}

Спасибо.

источник

2016-11-30 Tal Galili

Сначала я хочу, чтобы они поняли, как работает эта функция. Бонус будет объяснять эффективность. –

Как так? Не могли бы вы привести пример? –

Спасибо @RHertel Я исправил его. (ps: Я преподаю на иврите, так что я не использую английское правописание) –

Это, как я бы об объяснении рекурсивных функций в R:

Первый , Я согласен с @AEBilgrau в том, что факториал является хорошим примером рекурсии. (Лучше, чем Фибоначчи в моем opionion.)

Тогда я быстро пройти теоретическую основу, почему факторный может быть определена как рекурсивная функция, то просто как

4! = 4 * 3 * 2 * 1 = 4 * 3!

Тогда вы могли бы представить им соответствующую функцию рекурсивного R

fact=function(x) if (x==0) return(1) else return(x*fact(x-1)) 
fact(3) 
#6

но представить их также следующий вывод

#|fact(3) called 
#|fact(3) is calculated via 3*fact(2) 
#|fact(2) is unknown yet. Therefore calling fact(2) now 
#|Waiting for result from fact(2) 
#| fact(2) called 
#| fact(2) is calculated via 2*fact(1) 
#| fact(1) is unknown yet. Therefore calling fact(1) now 
#| Waiting for result from fact(1) 
#| | fact(1) called 
#| | fact(1) is calculated via 1*fact(0) 
#| | fact(0) is unknown yet. Therefore calling fact(0) now 
#| | Waiting for result from fact(0) 
#| | | fact(0) called 
#| | | fact(0)=1 per definition. Nothing to calculate. 
#| | | fact(0) returning 1 to waiting fact(1) 
#| | fact(1) received 1 from fact(0) 
#| | fact(1) can now calculate 1*fact(0)=1*1=1 
#| | fact(1) returning 1 to waiting fact(2) 
#| fact(2) received 1 from fact(1) 
#| fact(2) can now calculate 2*fact(1)=2*1=2 
#|fact(3) received 2 from fact(2) 
#|fact(3) can now calculate 3*fact(2)=3*2=6 
#[1] 6

как производное от

#helper function for formatting 
tabs=function(n) paste0("|",rep("\t",n),collapse="") 

fact=function(x) { 
    #determine length of call stack 
    sfl=length(sys.frames())-1 
    #we need to define tmp and tmp1 here because they are used in on.exit 
    tmp=NULL 
    tmp1=NULL 

    #on.exit will print the returned function value when we exit the function ... 
    #... i.e., when one function call is removed from the stack 
    on.exit({ 
    if (sfl>1) { 
     cat(tabs(sfl),"fact(",x,") returning ", 
      tmp," to waiting fact(",x+1,")\n",sep="") 
    } 
    }) 
    cat(tabs(sfl),"fact(",x,") called\n",sep="") 
    if (x==0) { 
    cat(tabs(sfl),"fact(0)=1 per definition. Nothing to calculate.\n",sep="") 
    #set tmp for printing in on.exit 
    tmp=1 
    return(1) 
    } else { 
    #print some info for students 
    cat(tabs(sfl),"fact(",x,") is calculated via ",x,"*fact(",x-1,")\n",sep="") 
    cat(tabs(sfl),"fact(",x-1, 
     ") is unknown yet. Therefore calling fact(",x-1,") now\n",sep="") 
    cat(tabs(sfl),"Waiting for result from fact(",x-1,")\n",sep="") 
    #call fact again 
    tmp1=fact(x-1) 
    #more info for students 
    cat(tabs(sfl),"fact(",x,") received ",tmp1," from fact(",x-1,")\n",sep="") 
    tmp=x*tmp1 
    cat(tabs(sfl),"fact(",x,") can now calculate ", 
     x,"*fact(",x-1,")=",x,"*",tmp1,"=",tmp,"\n",sep="") 
    return(tmp) 
    } 
} 

fact(3)

источник

2016-11-30 13:14:54 cryo111

печати значение переменной п в fib_r

print("iteraction at: ", n)

источник

2016-11-30 06:19:31

Я использовал в классе «печать» внутри рекурсивная функция, но я чувствовал, что этого недостаточно. –

Я думаю, что факторный функция является хорошим примером рекурсии. В сочетании с распечаткой (как другие полагают), кажется, как хороший способ, чтобы описать то, что происходит:

factorial <- function(n) { 
    cat("factorial(", n, ") was called.\n", sep = "") 
    if (n == 0) { 
    return(1) 
    } else { 
    return(n * factorial(n - 1)) 
    } 
} 

factorial(4) 
#factorial(4) was called. 
#factorial(3) was called. 
#factorial(2) was called. 
#factorial(1) was called. 
#factorial(0) was called. 
#[1] 24

Вы также можете затем реализовать нерекурсивную функцию факториала и сравнить вычислительную эффективность. Или, может быть, спросите их, что является проблематичным с вышеупомянутой реализацией (например, что происходит с factorial(-4)).

Что касается более правильной визуализации (а не просто простых примеров), то есть websites, которые иллюстрируют дерево рекурсии.

Редактировать:Googling recursion также полезный урок.

источник

2016-11-30 07:15:46

Мне это нравится, но этого может быть недостаточно. То, что студенты также должны видеть, - это то, как результаты затем передаются вверх до первого вызова «факториала». Я бы на самом деле использовал доску. – Roland

@Roland Я бы тоже использовал доску. Альтернативный веб-сайт, такой как тот, к которому я привязался сейчас, где можно было бы легко иллюстрировать дерево рекурсирования (как фибоначчи, так и факториала). –

Вот мой пример, вероятно, используется в целом ряде учебников:

recursive_sum <- function(n){ 
    if(n == 1) {print("Remember 1, add everything together"); return(n)} 
    print(paste0("Remember ", n, ", pass ", n-1, " to recursive function")) 
    n + recursive_sum(n-1) 
}

Выход:

> recursive_sum(4) 
[1] "Remember 4, pass 3 to recursive function" 
[1] "Remember 3, pass 2 to recursive function" 
[1] "Remember 2, pass 1 to recursive function" 
[1] "Remember 1, add everything together" 
[1] 10

источник

2016-11-30 08:01:16

Как эффективно визуализировать рекурсивную функцию?

ответ

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