평신도의 용어로 PHP를 사용하는 재귀 함수는 무엇입니까?
누구든지 평신도 언어와 예제를 사용하여 PHP에서 (피보나치를 사용하지 않고) 재귀 함수를 설명해 주시겠습니까? 나는 예를보고 있었지만 피보나치는 완전히 나를 잃었습니다!
미리 감사드립니다 ;-) 또한 웹 개발에 얼마나 자주 사용하십니까?
Laymens 용어 :
재귀 함수는 자신 을 호출하는 함수입니다.
좀 더 자세히 :
함수가 계속 자신을 호출하면 언제 중지해야하는지 어떻게 알 수 있습니까? 기본 사례라고하는 조건을 설정합니다. 기본 케이스는 언제 중지해야하는지 재귀 호출을 알려줍니다. 그렇지 않으면 무한 반복됩니다.
제가 수학에 대한 강한 배경 지식을 가지고 있기 때문에 저에게 좋은 학습 예는 계승 이었습니다 . 아래 설명에 따르면 계승 함수가 너무 많은 것 같습니다. 원하는 경우를 대비하여 여기에 남겨 두겠습니다.
function fact($n) {
if ($n === 0) { // our base case
return 1;
}
else {
return $n * fact($n-1); // <--calling itself.
}
}
웹 개발에서 재귀 함수를 사용하는 것과 관련하여 개인적으로 재귀 호출을 사용하지 않습니다. 재귀에 의존하는 것이 나쁜 습관이라고 생각하지는 않지만 첫 번째 옵션이되어서는 안됩니다. 제대로 사용하지 않으면 치명적일 수 있습니다.
디렉토리 예제와 경쟁 할 수는 없지만 이것이 도움이되기를 바랍니다.
(4/20/10) 업데이트 :
이 질문을 확인하는 것도 도움이 될 것입니다. 수락 된 답변은 재귀 함수가 어떻게 작동하는지 평신도 용어로 설명합니다. OP의 질문은 Java를 다루었지만 개념은 동일합니다.
예를 들어 주어진 디렉토리의 모든 하위 디렉토리에있는 모든 파일을 인쇄하는 것입니다 (이 디렉토리 내에 심볼릭 링크가 없어서 어떻게 든 기능을 손상시킬 수있는 경우). 모든 파일을 인쇄하는 의사 코드는 다음과 같습니다.
function printAllFiles($dir) {
foreach (getAllDirectories($dir) as $f) {
printAllFiles($f); // here is the recursive call
}
foreach (getAllFiles($dir) as $f) {
echo $f;
}
}
아이디어는 먼저 모든 하위 디렉토리를 인쇄 한 다음 현재 디렉토리의 파일을 인쇄하는 것입니다. 이 아이디어는 모든 하위 디렉토리에 적용되며 모든 하위 디렉토리에 대해이 함수를 재귀 적으로 호출하는 이유입니다.
당신이 특별한 디렉토리를 확인해야이 예를 시도하려는 경우 .와 .., 그렇지 않으면 호출에 박히면서 printAllFiles(".")모든 시간을. 또한 당신이 당신의 현재 작업 디렉토리가 무엇인지 무엇을 인쇄하고 확인해야합니다 (참조 opendir(), getcwd()...).
재귀는 스스로 반복되는 것입니다. 자체 내에서 자신을 호출하는 함수와 같습니다. 약간의 유사 예제로 설명하겠습니다.
친구들과 맥주를 마시고 있다고 상상해보십시오. 자정 전에 집에 오지 않으면 아내가 지옥을 줄 것입니다. 이를 위해 $ time이 자정에서 현재 음료를 마시고 집에 도착하는 데 걸리는 시간을 뺀 orderAndDrinkBeer ($ time) 함수를 만들어 보겠습니다.
따라서 바에 도착하면 첫 번째 맥주를 주문하고 술을 마시기 시작합니다.
$timeToGoHome = '23'; // Let's give ourselves an hour for last call and getting home
function orderAndDrinkBeer($timeToGoHome) { // Let's create the function that's going to call itself.
$beer = New Beer(); // Let's grab ourselves a new beer
$currentTime = date('G'); // Current hour in 24-hour format
while ($beer->status != 'empty') { // Time to commence the drinking loop
$beer->drink(); // Take a sip or two of the beer(or chug if that's your preference)
}
// Now we're out of the drinking loop and ready for a new beer
if ($currentTime < $timeToGoHome) { // BUT only if we got the time
orderAndDrinkBeer($timeToGoHome); // So we make the function call itself again!
} else { // Aw, snap! It is time :S
break; // Let's go home :(
}
}
이제 맥주를 충분히 마시지 못해 술에 취해 아내가 제 시간에 집에 있어도 소파에서 잠을 잘 수 있기를 바라자 -.-
그러나 예, 그것은 재귀가 진행되는 방식입니다.
자신을 호출하는 함수입니다. 나무와 같이 반복되는 특정 데이터 구조를 걷는 데 유용합니다. HTML DOM이 전형적인 예입니다.
자바 스크립트의 트리 구조와 트리를 '걷는'재귀 함수의 예입니다.
1
/ \
2 3
/ \
4 5
-
var tree = {
id: 1,
left: {
id: 2,
left: null,
right: null
},
right: {
id: 3,
left: {
id: 4,
left: null,
right: null
},
right: {
id: 5,
left: null,
right: null
}
}
};
트리를 걷기 위해 동일한 함수를 반복적으로 호출하여 현재 노드의 자식 노드를 동일한 함수에 전달합니다. 그런 다음 함수를 다시 왼쪽 노드에서 호출 한 다음 오른쪽에서 호출합니다.
이 예에서는 트리의 최대 깊이를 얻습니다.
var depth = 0;
function walkTree(node, i) {
//Increment our depth counter and check
i++;
if (i > depth) depth = i;
//call this function again for each of the branch nodes (recursion!)
if (node.left != null) walkTree(node.left, i);
if (node.right != null) walkTree(node.right, i);
//Decrement our depth counter before going back up the call stack
i--;
}
마지막으로 함수를 호출합니다.
alert('Tree depth:' + walkTree(tree, 0));
재귀를 이해하는 가장 좋은 방법은 런타임에 코드를 단계별로 살펴 보는 것입니다.
간단히 말해 : 재귀 함수는 자신을 호출하는 함수입니다.
함수가 정의되지 않고 유한 한 시간 동안 작업을 수행하기 위해 자신을 호출 할 때 매우 간단합니다. 내 코드의 예, 다단계 카테고리 트리를 채우는 함수
function category_tree ($ parent = 0, $ sep = '')
{
$ q = "select id, name from categorye where parent_id =". $ parent;
$ rs = mysql_query ($ q);
while ($ rd = mysql_fetch_object ($ rs))
{
echo ( 'id.' "> '. $ sep. $ rd-> 이름.' ');
category_tree ($ rd-> id, $ sep .'-- ');
}
}
재귀는 "완료 될 때까지이 작업을 다시 수행하십시오"라고 말하는 멋진 방법입니다.
두 가지 중요한 사항 :
- 기본 사례-달성해야 할 목표가 있습니다.
- 테스트-가는 곳이 있는지 확인하는 방법.
간단한 작업을 상상해보십시오. 책 더미를 알파벳순으로 정렬합니다. 간단한 과정은 처음 두 권의 책을 가져 와서 분류하는 것입니다. 자, 여기에 재귀 부분이 있습니다. 책이 더 있습니까? 그렇다면 다시 수행하십시오. "다시해라"는 재귀입니다. "더 많은 책이 있습니까"가 시험입니다. 그리고 "아니, 더 이상 책은 없습니다"가 기본 케이스입니다.
내가 여기에 있다는 것을 알았을 때 찾은 최고의 설명 : http://www.elated.com/articles/php-recursive-functions/
한 가지 이유가 있습니다.
호출 된 함수가 메모리에 생성됩니다 (새 인스턴스가 생성됨).
따라서 재귀 함수 는 자체 호출이 아니라 다른 인스턴스를 호출하므로 메모리에있는 하나의 함수가 마법을 수행하지 않습니다. 몇 가지 값을 반환하는 메모리의 인스턴스 두 개-예를 들어 함수 a가 함수 b를 호출 할 때이 동작은 동일합니다. 두 개의 인스턴스가 있으며 재귀 함수가 자신의 새 인스턴스를 호출합니다.
종이에 인스턴스로 메모리를 그려보십시오.
재귀는 루프의 대안이며 코드에 더 명확하거나 우아함을 제공하는 경우는 거의 없습니다. Progman의 대답에 좋은 예가 주어졌습니다. 만약 그가 재귀를 사용하지 않는다면 그가 현재 어떤 디렉토리 (상태라고 함)에 있는지 추적해야 할 것입니다. 재귀는 스택 (변수가있는 영역 메서드의 반환 주소가 저장 됨)
표준 예제 factorial과 Fibonacci는 루프로 대체하기 쉽기 때문에 개념을 이해하는 데 유용하지 않습니다.
기본적으로 이것은. 끝날 때까지 자꾸 부른다
void print_folder(string root)
{
Console.WriteLine(root);
foreach(var folder in Directory.GetDirectories(root))
{
print_folder(folder);
}
}
루프에서도 작동합니다!
void pretend_loop(int c)
{
if(c==0) return;
print "hi";
pretend_loop(c-);
}
인터넷 검색을 시도 할 수도 있습니다. "이것을 의미 했습니까?"(클릭하십시오 ...)를 적어 둡니다. http://www.google.com/search?q=recursion&spell=1
다음은 실용적인 예입니다 (이미 좋은 예가 몇 개 있습니다). 거의 모든 개발자에게 유용한 것을 추가하고 싶었습니다.
어느 시점에서 개발자는 API 또는 일부 유형의 개체 또는 배열의 응답으로 개체를 구문 분석해야합니다.
이 함수는 처음에는 매개 변수 만 포함 할 수있는 객체를 구문 분석하기 위해 호출되지만 객체에 다른 객체 나 배열도 포함되어 있으면 어떻게 될까요? 이 문제를 해결해야하며 대부분의 경우 기본 함수가 이미이 작업을 수행하므로 함수는 자신을 다시 호출하고 (키 또는 값이 객체 또는 배열인지 확인한 후)이 새 객체 또는 배열을 구문 분석합니다. 궁극적으로 반환되는 것은 가독성을 위해 한 줄에 각 매개 변수를 생성하는 문자열이지만, 값을 로그 파일에 쉽게 기록하거나 DB 등에 삽입 할 수 있습니다.
$prefix끝 변수를 설명하는 데 도움이되는 부모 요소를 사용 하는 매개 변수를 추가하여 값이 무엇과 관련된 지 확인할 수 있습니다. null 값과 같은 것은 포함되지 않지만이 예제에서 수정할 수 있습니다.
개체가있는 경우 :
$apiReturn = new stdClass();
$apiReturn->shippingInfo = new stdClass();
$apiReturn->shippingInfo->fName = "Bill";
$apiReturn->shippingInfo->lName = "Test";
$apiReturn->shippingInfo->address1 = "22 S. Deleware St.";
$apiReturn->shippingInfo->city = "Chandler";
$apiReturn->shippingInfo->state = "AZ";
$apiReturn->shippingInfo->zip = 85225;
$apiReturn->phone = "602-312-4455";
$apiReturn->transactionDetails = array(
"totalAmt" => "100.00",
"currency" => "USD",
"tax" => "5.00",
"shipping" => "5.00"
);
$apiReturn->item = new stdClass();
$apiReturn->item->name = "T-shirt";
$apiReturn->item->color = "blue";
$apiReturn->item->itemQty = 1;
사용 :
var_dump($apiReturn);
다음을 반환합니다.
object (stdClass) # 1 (4) {[ "shippingInfo"] => object (stdClass) # 2 (6) {[ "fName"] => string (4) "Bill"[ "lName"] => string ( 4) "Test"[ "address1"] => string (18) "22 S. Deleware St." [ "city"] => string (8) "Chandler"[ "state"] => string (2) "AZ"[ "zip"] => int (85225)} [ "phone"] => string (12 ) "602-312-4455"[ "transactionDetails"] => array (4) {[ "totalAmt"] => string (6) "100.00"[ "currency"] => string (3) "USD"[ " tax "] => string (4)"5.00 "["shipping "] => string (4)"5.00 "} ["item "] => object (stdClass) # 3 (3) {["name "] = > string (7) "티셔츠"[ "color"] =>
다음은 각 매개 변수에 대해 줄 바꿈이있는 문자열로 구문 분석하는 코드입니다.
function parseObj($obj, $prefix = ''){
$stringRtrn = '';
foreach($obj as $key=>$value){
if($prefix){
switch ($key) {
case is_array($key):
foreach($key as $k=>$v){
$stringRtrn .= parseObj($key, $obj);
}
break;
case is_object($key):
$stringRtrn .= parseObj($key, $obj);
break;
default:
switch ($value) {
case is_array($value):
$stringRtrn .= parseObj($value, $key);
break;
case is_object($value):
$stringRtrn .= parseObj($value, $key);
break;
default:
$stringRtrn .= $prefix ."_". $key ." = ". $value ."<br>";
break;
}
break;
}
} else { // end if($prefix)
switch($key){
case is_array($key):
$stringRtrn .= parseObj($key, $obj);
break;
case is_object($key):
$stringRtrn .= parseObj($key, $obj);
break;
default:
switch ($value) {
case is_array($value):
$stringRtrn .= parseObj($value, $key);
break;
case is_object($value):
$stringRtrn .= parseObj($value, $key);
break;
default:
$stringRtrn .= $key ." = ". $value ."<br>";
break;
} // end inner switch
} // end outer switch
} // end else
} // end foreach($obj as $key=>$value)
return $stringRtrn;
} // END parseObj()
그러면 다음과 같이 객체가 반환됩니다.
shippingInfo_fName = Bill
shippingInfo_lName = Test
shippingInfo_address1 = 22 S. Deleware St.
shippingInfo_city = Chandler
shippingInfo_state = AZ
shippingInfo_zip = 85225
phone = 602-312-4455
transactionDetails_totalAmt = 100.00
transactionDetails_currency = USD
transactionDetails_tax = 5.00
transactionDetails_shipping = 5.00
item_name = T-shirt
item_color = blue
item_itemQty = 1
나는 한 중첩 된 스위치 와 혼동을 피하기 위해 문을 if . . . ifelse . . . else하지만, 거의 한이었다. 도움이된다면 if 조건문을 요청하면 필요한 사람들을 위해 붙여 넣을 수 있습니다.
디렉토리 트리를 살펴 보는 것이 좋은 예입니다. 배열을 처리하는 것과 유사한 작업을 수행 할 수 있습니다. 다음은 문자열, 간단한 문자열 배열 또는 모든 깊이의 중첩 된 문자열 배열을 처리하는 정말 간단한 재귀 함수입니다. 문자열에서 'hello'의 인스턴스를 'goodbye'로 바꾸거나 배열의 값 또는 하위 배열 :
function replaceHello($a) {
if (! is_array($a)) {
$a = str_replace('hello', 'goodbye', $a);
} else {
foreach($a as $key => $value) {
$a[$key] = replaceHello($value);
}
}
return $a
}
어떤 시점에서 처리중인 "물건"이 배열이 아니기 때문에 종료 할시기를 알고 있습니다. 예를 들어 replaceHello ( 'hello')를 호출하면 'goodbye'가 반환됩니다. 문자열 배열을 보내면 배열의 모든 구성원에 대해 한 번씩 자신을 호출 한 다음 처리 된 배열을 반환합니다.
Anthony Forloney의 예에 특정 값 (예 : "1")을 추가하면 모든 것이 명확 해집니다.
function fact(1) {
if (1 === 0) { // our base case
return 1;
}
else {
return 1 * fact(1-1); // <--calling itself.
}
}
실물:
function fact($n) {
if ($n === 0) { // our base case
return 1;
}
else {
return $n * fact($n-1); // <--calling itself.
}
}
다음은 재귀를 사용한 팩토리얼의 매우 간단한 예입니다.
팩토리얼은 매우 쉬운 수학 개념입니다. 그들은 5처럼 쓰여졌습니다! 이것은 5 * 4 * 3 * 2 * 1을 의미합니다. 그래서 6! 720과 4입니다! 24입니다.
function factorial($number) {
if ($number < 2) {
return 1;
} else {
return ($number * factorial($number-1));
}
}
이것이 당신에게 유용하기를 바랍니다. :)
간단한 예 재귀 (Y) 작동
<?php function factorial($y,$x) { if ($y < $x) { echo $y; } else { echo $x; factorial($y,$x+1); } } $y=10; $x=0; factorial($y,$x); ?>
Kaprekar 상수에 사용되는 재귀
function KaprekarsConstant($num, $count = 1) {
$input = str_split($num);
sort($input);
$ascendingInput = implode($input);
$descendingInput = implode(array_reverse($input));
$result = $ascendingInput > $descendingInput
? $ascendingInput - $descendingInput
: $descendingInput - $ascendingInput;
if ($result != 6174) {
return KaprekarsConstant(sprintf('%04d', $result), $count + 1);
}
return $count;
}
The function keeps calling itself with the result of the calculation until it reaches Kaprekars constant, at which it will return the amount of times the calculations was made.
/edit For anyone that doesn't know Kaprekars Constant, it needs an input of 4 digits with at least two distinct digits.
I don't find the examples helpful either. You cant solve two problems at once when there is mathematics involved your mind is switching between two problems. Enough talking
Example:
I have a function where i am exploding strings into array based on : delimiter.
public function explodeString($string)
{
return explode(":", $string);
}
I have another function where i am taking strings as input
public function doRec()
{
$strings = [
'no:go',
'hello:world',
'nested' => [
'iam:good',
'bad:array',
'bad:how',
'bad:about',
]
];
$response = [];
foreach ($strings as $string) {
array_push($response,$this->explodeString($string));
}
return $response;
}
The problem is, my input has a nested array and my explodeString function recieve a type string. I can rewrite some code in explodeString function to adjust to this but i still need the same function to do the same operation on my string. Thats where i can call the method recursively within. So here is the final explodeString function with recursion.
public function explodeString($string)
{
if (is_array($string)) {
$combine = [];
foreach ($string as $str) {
array_push($combine, $this->explodeString($str));
}
return $combine;
}
return explode(":", $string);
}
참고URL : https://stackoverflow.com/questions/2648968/what-in-laymans-terms-is-a-recursive-function-using-php
'IT박스' 카테고리의 다른 글
| Erlang을 사용하여 "반대"를 결정한 이유는 무엇입니까? (0) | 2020.10.26 |
|---|---|
| 'Z'리터럴로 날짜를 구문 분석하는 simpledateformat (0) | 2020.10.26 |
| 암호를 키 또는 IV로 직접 사용하는 대신 Rfc2898DeriveBytes 클래스 (.NET)를 사용해야하는 이유는 무엇입니까? (0) | 2020.10.26 |
| 반복하지 않고 ArrayList의 합계 가능성이 있습니까? (0) | 2020.10.26 |
| MySQL match () against ()-관련성 및 열별 정렬? (0) | 2020.10.26 |