Понимание рекурсии

Question

Я изо всех сил пытаюсь понять эту рекурсию, используемую в примере динамического программирования. Может кто-нибудь объяснить работу этого. Цель состоит в том, чтобы найти наименьшее количество монет для стоимости.

// F (п) = 1 + мин е (п-д) для всех denomimations d

Псевдокод:

int memo[128]; //initialized to -1 

int min_coin(int n) 
{ 
    if(n < 0) return INF; 
    if(n == 0) return 0; 
    if(memo[n] != -1) 

    int ans = INF; 
    for(int i = 0; i < num_denomination; ++i) 
    { 
     ans = min(ans, min_coin(n - denominations[i])); 
    } 
    return memo[n] = ans+1; //when does this get called? 

} 

Answer 1

Этот частный пример объясняется очень хорошо в этом article на TopCoder.

В основном это рекурсии с использованием решений для небольших проблем (наименьшее количество монет для меньшего п) , чтобы найти решение для общей проблемы. Аспект динамического программирования это memoization решений проблем, поэтому их не нужно пересчитывать каждый раз.

И да - в его комментарии упоминается {} отсутствующее как ring0 - рекурсия должна выполняться только в том случае, если суба проблема не была решена ранее.

Answer 2

Чтобы ответить на вопрос владельца , когда это вызвано?: в решении, основанном на рекурсивной программе, одна и та же функция вызывается сама по себе ... но в конечном итоге возвращается ... Когда она возвращается? с момента, когда функция перестала называть себя

f(a) { 
    if (a > 0) f(a-1); 
    display "x" 
} 

f(5); 

f(5) бы называть F (4), в свою очередь называть F (3) следует, что называть F (2), который вызывает F (1) вызова F (0).

f(0) имеет a быть 0, так что не вызывает f(), и отображает "х", то возвращает. Он возвращается к предыдущему f(1), который после вызова f(0) - done - отображает также «x». f(1) заканчивается, f (2) отображает «x», ..., до f (5). Вы получаете 6 "x".

Answer 3

В других терминах, из которых уже было упомянуто ring0 - когда программа достигает базового футляра и начинает разматываться, поднимаясь вверх по стеклу (кадрам вызовов). Для аналогичного случая с использованием factorial example see this.

#!/usr/bin/env perl 

use strict; 
use IO::Handle; 
use Carp qw(cluck); 

STDOUT->autoflush(1); 
STDERR->autoflush(1); 

sub factorial { 
    my $v = shift; 

    dummy_func(); 
    return 1 if $v == 1; 
    print "Variable v value: $v and it's address:", \$v, "\ncurrent sub factorial addr:", \&factorial, "\n","-"x40; 
    return $v * factorial($v - 1); 
} 

sub dummy_func { 
    cluck; 
} 

factorial(5);