瞭解遞歸

Question

我很努力地理解動態編程示例中使用的這種遞歸。任何人都可以解釋這個工作。目標是找到一個值最少的硬幣數量。

// F（N）= 1架+分鐘F（N-d）所有denomimationsð

僞代碼：

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的很好的解釋。

基本上這是遞歸使用的解決方案，較小的問題（最少數目的硬幣的一個較小的n）的找到整個問題溶液。這是動態編程方面的子問題的解決方案的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) - 完成後 - 也顯示「x」。 （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);