పునరావృత మరియు పునరావృత ఫార్ములాను అర్థం చేసుకోవడం

మరల

పునరావృతం అనేది ఒక ప్రక్రియ యొక్క పునరావృతం. పాఠశాలకు వెళ్ళే విద్యార్థి గ్రాడ్యుయేషన్ వరకు ప్రతిరోజూ పాఠశాలకు వెళ్ళే విధానాన్ని పునరావృతం చేస్తాడు. మేము ఉత్పత్తులను కొనడానికి నెలకు ఒకటి లేదా రెండుసార్లు కిరాణా దుకాణానికి వెళ్తాము. మేము ప్రతి నెలా ఈ విధానాన్ని పునరావృతం చేస్తాము. గణితంలో, ఫైబొనాక్సీ సీక్వెన్స్ టాస్క్ రిపీట్ యొక్క లక్షణాలను కూడా అనుసరిస్తుంది. మొదటి రెండు సంఖ్యలు 0 మరియు 1 ఉన్న ఫైబొనాక్సీ క్రమాన్ని పరిశీలిద్దాం, మిగతా అన్ని సంఖ్యలు మునుపటి రెండు సంఖ్యల మొత్తం.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

పునరావృత దశలు

ఫైబొనాక్సీ సూత్రాన్ని ఇలా వ్రాయవచ్చు,

F (n) = F (n - 1) + F (n - 2)
ఫైబొనాక్సీ (0) = 0
ఫైబొనాక్సీ (1) = 1
ఫైబొనాక్సీ (2) = ఫైబొనాక్సీ (1) + ఫైబొనాక్సీ (0) = 1 + 0 = 1
ఫైబొనాక్సీ (3) = ఫైబొనాక్సీ (2) + ఫైబొనాక్సీ (1) = 1 + 1 = 2
ఫైబొనాక్సీ (4) = ఫైబొనాక్సీ (3) + ఫైబొనాక్సీ (2) = 2 + 1 = 3
ఫైబొనాక్సీ (5) = ఫైబొనాక్సీ (4) + ఫైబొనాక్సీ (3) = 3 + 2 = 5
ఫైబొనాక్సీ (6) = ఫైబొనాక్సీ (5) + ఫైబొనాక్సీ (4) = 5 + 3 = 8

క్రింద ఇవ్వబడిన అల్గోరిథం n వ ఫైబొనాక్సీ సంఖ్యను అందిస్తుంది.

పునరావృతం

ప్రతిసారీ మనకు క్రొత్త ఫైబొనాక్సీ సంఖ్య (n వ సంఖ్య) వచ్చినప్పుడు, ఆ n వ సంఖ్య వాస్తవానికి (n - 1) వ సంఖ్య (n + 1) వ ఫైబొనాక్సీని మన తదుపరి n వ ఫైబొనాక్సీగా కనుగొన్నప్పుడు. పైన పేర్కొన్న పునరావృత దశలను మనం చూస్తున్నప్పుడు: n = 2 అయితే
ఫైబొనాక్సీ (2) = ఫైబొనాక్సీ (2 - 1) + ఫైబొనాక్సీ (2 - 2) = ఫైబొనాక్సీ (1) + ఫైబొనాక్సీ (0) = 1 + 0 = 1

ఇప్పుడు, మేము ఫైబొనాక్సీ (3) ను ఉత్పత్తి చేయాలనుకుంటున్నాము, అంటే n = 3.

ఫైబొనాక్సీ (3) = ఫైబొనాక్సీ (3 - 1) + ఫైబొనాక్సీ (3 - 2) = ఫైబొనాక్సీ (2) + ఫైబొనాక్సీ (1) = 1 + 1 = 2
అంటే, ప్రతిసారీ n ప్రస్తుత (n - 1) వ విలువను పెంచుతుంది మరియు (n - 2) వ ఫైబొనాక్సీ కూడా పెరుగుతుంది. కానీ ప్రతి n కి (n - 1) వ మరియు (n - 2) వ ఫైబొనాక్సీని ట్రాక్ చేయడం చాలా అలసిపోతుంది. పునరావృత పనిని స్వయంగా పునరావృతం చేయడానికి తనను తాను పిలిచే ఒక పద్ధతిని రాయడం ఎలా?

తనను తాను పిలిచే ఒక పద్ధతికి పునరావృత పద్ధతి అని పేరు పెట్టారు. పునరావృత పద్ధతిలో తప్పనిసరిగా బేస్ కేసు ఉండాలి, అక్కడ ప్రోగ్రామ్ తనను తాను పిలవడం ఆపివేస్తుంది. ఫైబొనాక్సీ సిరీస్ కోసం మా బేస్ కేసు ఫైబొనాక్సీ (0) = 0 మరియు ఫైబొనాక్సీ (1) = 1. లేకపోతే, ఫైబొనాక్సీ పద్ధతి తనను తాను రెండుసార్లు పిలుస్తుంది - ఫైబొనాక్సీ (ఎన్ - 1) మరియు ఫైబొనాక్సీ (ఎన్ - 2). అప్పుడు అది ఫైబొనాక్సీ (ఎన్) పొందడానికి వాటిని జతచేస్తుంది. N వ ఫైబొనాక్సీని కనుగొనడానికి పునరావృత పద్ధతి ఇలా వ్రాయవచ్చు -

మేము జాగ్రత్తగా చూస్తే, పునరావృతం స్టాక్ యొక్క ఆస్తిని అనుసరిస్తుంది. ఇది సమస్య యొక్క పరిష్కారాన్ని పొందడానికి చిన్న ఉప సమస్యలను పరిష్కరిస్తుంది. N> 1 కొరకు, ఇది చివరి పంక్తిని అమలు చేస్తుంది. కాబట్టి, n = 6 అయితే, ఫంక్షన్ ఫైబొనాక్సీ (6 - 1) మరియు ఫైబొనాక్సీ (6 - 2) ను పిలుస్తుంది మరియు జతచేస్తుంది. ఫైబొనాక్సీ (6 - 1) లేదా ఫైబొనాక్సీ (5) ఫైబొనాక్సీ (5 - 1) మరియు ఫైబొనాక్సీ (5 - 2) ను పిలుస్తుంది మరియు జతచేస్తుంది. ఫైబొనాక్సీ (0) = 0 లేదా ఫైబొనాక్సీ (1) = 1. దాని బేస్ కేస్ విలువకు 6 చేరుకునే వరకు ఈ పునరావృతం కొనసాగుతుంది. ఇది బేస్ కేస్‌ను తాకిన తర్వాత అది రెండు బేస్ విలువలను జోడించి ఫైబొనాక్సీ విలువను పొందే వరకు పెరుగుతుంది ( 6). క్రింద పునరావృత చెట్టు ప్రాతినిధ్యం ఉంది.

పునరావృత చెట్టు

మనం చూడగలిగినట్లుగా, పునరావృతం ఎంత శక్తివంతంగా ఉంటుంది. కోడ్ యొక్క ఒకే ఒక పంక్తి మాత్రమే పైన చెట్టును తయారు చేస్తోంది (పైన ఉన్న కోడ్ యొక్క చివరి పంక్తి బేస్ కేసులతో సహా). పునరావృతం ఒక స్టాక్‌ను నిర్వహిస్తుంది మరియు ఇది బేస్ కేసుకు చేరే వరకు లోతుకు వెళుతుంది. డైనమిక్ ప్రోగ్రామింగ్ (డిపి): పునరావృతం అర్థం చేసుకోవడం సులభం మరియు కోడ్ కానీ సమయం మరియు జ్ఞాపకశక్తి పరంగా ఖరీదైనది కావచ్చు. క్రింద ఉన్న పునరావృత చెట్టును చూడండి. ఫైబ్ (4) తో ప్రారంభమయ్యే ఎడమ సబ్‌ట్రీ మరియు ఫైబ్ (4) తో ప్రారంభమయ్యే కుడి సబ్‌ట్రీ సరిగ్గా ఒకే విధంగా ఉంటాయి. వారు అదే ఫలితాన్ని 3 గా ఉత్పత్తి చేస్తారు, కాని ఒకే పనిని రెండుసార్లు చేస్తున్నారు. N ఒక పెద్ద సంఖ్య అయితే (ఉదాహరణ: 500000) అప్పుడు పునరావృతం ఒక ప్రోగ్రామ్‌ను చాలా నెమ్మదిగా చేస్తుంది, ఎందుకంటే ఇది ఒకే ఉప పనిని అనేకసార్లు పిలుస్తుంది.

పునరావృతం చెట్టు-వృత్తాకార

ఈ సమస్యను నివారించడానికి డైనమిక్ ప్రోగ్రామింగ్ ఉపయోగించవచ్చు. డైనమిక్ ప్రోగ్రామింగ్‌లో, ఒకే రకమైన భవిష్యత్ పనిని పరిష్కరించడానికి మేము గతంలో పరిష్కరించిన ఉప టాస్క్‌ని ఉపయోగించవచ్చు. అసలు సమస్యను పరిష్కరించడానికి పనిని తగ్గించడానికి ఇది ఒక మార్గం. ఇంతకుముందు పరిష్కరించిన సబ్ టాస్క్ పరిష్కారాలను నిల్వ చేసే శ్రేణి ఫైబ్ [] ను కలిగి ఉండండి. ఫైబ్ [0] = 0 మరియు ఫైబ్ [1] = 1. మనకు ఇప్పటికే తెలుసు. ఈ రెండు విలువలను నిల్వ చేద్దాం. ఇప్పుడు, ఫైబ్ యొక్క విలువ ఏమిటి [2]? ఫైబ్ [0] = 0 మరియు ఫైబ్ [1] = 1 ఇప్పటికే నిల్వ చేయబడినందున మనం ఫైబ్ [2] = ఫైబ్ [1] + ఫైబ్ [0] అని చెప్పాలి మరియు అంతే. మనం అదే విధంగా ఫైబ్ [3], ఫైబ్ [4], ఫైబ్ [5], ……, ఫైబ్ [ఎన్] ను ఉత్పత్తి చేయవచ్చు. అసలు పని పరిష్కరించబడనంతవరకు మునుపటి ఉప టాస్క్‌ను పొందడానికి గతంలో పరిష్కరించబడిన ఉప-టాస్క్‌లు పిలువబడుతున్నాయి, తద్వారా అనవసరమైన గణనను తగ్గిస్తుంది.