了解递归

我很努力地理解动态编程示例中使用的这种递归。任何人都可以解释这个工作。目标是找到一个值最少的硬币数量。了解递归

// 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? 

}

来源

2010-09-29 Neerad

if（memo [n]！= -1）后缺少一些'{}'？ – 2010-09-29 03:55:18

我不知道要纠正它。这是作为一个例子在这里http://www.ugrad.cs.ubc.ca/~cs490/sec202/notes/dp/DP%201.pdf – Neerad 2010-09-29 03:59:18

这个特殊的例子是在此article在TopCoder的很好的解释。

基本上这是递归使用的解决方案，较小的问题（最少数目的硬币的一个较小的n）的找到整个问题溶液。这是动态编程方面的子问题的解决方案的memoization，所以他们不必每次重新计算。

是的 - 在评论中提到的ring0缺少{}，只有在子问题没有被解决之前，才会执行递归。

来源

2010-09-29 04:06:50 BrokenGlass

要回答店主的问题什么时候这被调用？：在基于递归程序的解决方案中，相同的函数被自己调用...但最终返回...什么时候返回？从时间函数不再调用自身

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”。

来源

2010-09-29 04:16:15

从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);

来源

2013-02-21 01:44:49 Shiva

回答

相关问题